Data Structure

Buffer

Traffic light

Description

https://www.codewars.com/kata/58649884a1659ed6cb000072/

You’re writing code to control your town’s traffic lights. You need a function to handle each change from green, to yellow, to red, and then to green again.

Complete the function that takes a string as an argument representing the current state of the light and returns a string representing the state the light should change to.

For example, when the input is green, output should be yellow.

def update_light(current):
    pass

Solutions

def update_light(current):
    lights_pairs = {"green": "yellow", "yellow": "red", "red": "green"}
    
    for key, value in lights_pairs.items():
        if current == key:
            return value

def update_light(current):
    return {"green": "yellow", "yellow": "red", "red": "green"}[current]

class Node:
    def __init__(self, state):
        self.state = state
        self.next = None

class TrafficLight:
    def __init__(self):
        # 创建链表节点
        self.green = Node("green")
        self.yellow = Node("yellow")
        self.red = Node("red")
        
        # 链接节点
        self.green.next = self.yellow
        self.yellow.next = self.red
        self.red.next = self.green
        
        # 初始化当前状态为 green
        self.current = self.green
    
    def change_light(self, current_state):
        # 遍历链表查找当前状态
        temp = self.green
        while temp:
            if temp.state == current_state:
                # 更新当前状态
                self.current = temp.next
                return self.current.state
            temp = temp.next
        return "Invalid State"

traffic_light = TrafficLight()
print(traffic_light.change_light("green"))   # 输出: "yellow"
print(traffic_light.change_light("yellow"))  # 输出: "red"
print(traffic_light.change_light("red"))     # 输出: "green"

Reverse or rotate?

Description

https://www.codewars.com/kata/56b5afb4ed1f6d5fb0000991/

The input is a string str of digits. Cut the string into chunks (a chunk here is a substring of the initial string) of size sz (ignore the last chunk if its size is less than sz).

If the sum of a chunk’s digits is divisible by 2, reverse that chunk; otherwise rotate it to the left by one position. Put together these modified chunks and return the result as a string.

If

• sz is <= 0 or if str == "" return ""
• sz is greater (>) than the length of str it is impossible to take a chunk of size sz hence return "".

Examples:
("123456987654", 6) --> "234561876549"
("123456987653", 6) --> "234561356789"
("66443875", 4) --> "44668753"
("66443875", 8) --> "64438756"
("664438769", 8) --> "67834466"
("123456779", 8) --> "23456771"
("", 8) --> ""
("123456779", 0) --> "" 
("563000655734469485", 4) --> "0365065073456944"
Example of a string rotated to the left by one position:
s = "123456" gives "234561".

Solution

def rev_rot(strng, sz):
    if sz <= 0 or not strng or sz > len(strng):
        return ""
    
    result = []
    for i in range(0, len(strng), sz):
        chunk = strng[i:i+sz]
        if len(chunk) < sz:
            continue
        
        digit_sum = sum(int(char) for char in chunk)
        if digit_sum % 2 == 0:
            result.append(chunk[::-1])
        else:
            result.append(chunk[1:] + chunk[0])
    
    return "".join(result)

Strings Mix

Description

https://www.codewars.com/kata/5629db57620258aa9d000014/

Given two strings s1 and s2, we want to visualize how different the two strings are. We will only take into account the lowercase letters (a to z). First let us count the frequency of each lowercase letters in s1 and s2.

s1 = "A aaaa bb c"

s2 = "& aaa bbb c d"

s1 has 4 'a', 2 'b', 1 'c'

s2 has 3 'a', 3 'b', 1 'c', 1 'd'

So the maximum for 'a' in s1 and s2 is 4 from s1; the maximum for 'b' is 3 from s2. In the following we will not consider letters when the maximum of their occurrences is less than or equal to 1.

We can resume the differences between s1 and s2 in the following string: "1:aaaa/2:bbb" where 1 in 1:aaaa stands for string s1 and aaaa because the maximum for a is 4. In the same manner 2:bbb stands for string s2 and bbb because the maximum for b is 3.

The task is to produce a string in which each lowercase letters of s1 or s2 appears as many times as its maximum if this maximum is strictly greater than 1; these letters will be prefixed by the number of the string where they appear with their maximum value and :. If the maximum is in s1 as well as in s2 the prefix is =:.

In the result, substrings (a substring is for example 2:nnnnn or 1:hhh; it contains the prefix) will be in decreasing order of their length and when they have the same length sorted in ascending lexicographic order (letters and digits - more precisely sorted by codepoint); the different groups will be separated by '/'. See examples and “Example Tests”.

Hopefully other examples can make this clearer.

s1 = "my&friend&Paul has heavy hats! &"
s2 = "my friend John has many many friends &"
mix(s1, s2) # --> "2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss"

s1 = "mmmmm m nnnnn y&friend&Paul has heavy hats! &"
s2 = "my frie n d Joh n has ma n y ma n y frie n ds n&"
mix(s1, s2) # --> "1:mmmmmm/=:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss"

s1="Are the kids at home? aaaaa fffff"
s2="Yes they are here! aaaaa fffff"
mix(s1, s2) # --> "=:aaaaaa/2:eeeee/=:fffff/1:tt/2:rr/=:hh"

# Note for Swift, R, PowerShell
# The prefix =: is replaced by E:

s1 = "mmmmm m nnnnn y&friend&Paul has heavy hats! &"
s2 = "my frie n d Joh n has ma n y ma n y frie n ds n&"
mix(s1, s2) # --> "1:mmmmmm/E:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/E:ee/E:ss"

Solution

from collections import Counter

def mix(s1, s2):
    '''
    1. Count Frequencies: Count the occurrences of each lowercase letter in both strings s1 and s2.

    2. Determine Maximum Frequencies: For each letter that appears in either s1 or s2, determine the maximum frequency of that letter between the two strings.

    3. Build Result Strings: Construct the result strings based on the maximum frequencies:
        - If a letter's maximum frequency is greater than 1, include it in the result.
        - Use 1: to prefix the result if the letter's maximum frequency is from s1.
        - Use 2: to prefix the result if the letter's maximum frequency is from s2.
        - Use = to prefix the result if the letter's maximum frequency is from both s1 and s2.
    4 Sort and Format: Sort the results first by the length of the result strings in descending order. If the lengths are the same, sort them lexicographically. Finally, join the results with '/'.
    '''

    # Count frequencies of lowercase letters in both strings
    counter1 = Counter(c for c in s1 if c.islower())
    counter2 = Counter(c for c in s2 if c.islower())
    
    # Get all unique letters that appear in either string
    all_letters = set(counter1.keys()).union(counter2.keys())
    
    results = []
    
    for letter in sorted(all_letters):
        freq1 = counter1.get(letter, 0)
        freq2 = counter2.get(letter, 0)
        
        max_freq = max(freq1, freq2)
        
        if max_freq > 1:
            if freq1 == max_freq and freq2 == max_freq:
                results.append(f"=:{letter * max_freq}")
            elif freq1 == max_freq:
                results.append(f"1:{letter * max_freq}")
            elif freq2 == max_freq:
                results.append(f"2:{letter * max_freq}")
    
    # Sort results: first by length descending, then lexicographically
    results.sort(key=lambda x: (-len(x), x))
    
    # Join results with '/'
    return '/'.join(results)

def mix(s1, s2):
    hist = {}
    for ch in "abcdefghijklmnopqrstuvwxyz":
        val1, val2 = s1.count(ch), s2.count(ch)
        if max(val1, val2) > 1:
            which = "1" if val1 > val2 else "2" if val2 > val1 else "="
            hist[ch] = (-max(val1, val2), which + ":" + ch * max(val1, val2))
    return "/".join(hist[ch][1] for ch in sorted(hist, key=lambda x: hist[x]))

Hash Table (Hash Map)

Two Sum

Description

https://www.codewars.com/kata/52c31f8e6605bcc646000082/

Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value. The indices of these items should then be returned in a tuple / list (depending on your language) like so: (index1, index2).

For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.

The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).

Based on: https://leetcode.com/problems/two-sum/

two_sum([1, 2, 3], 4) # returns (0, 2) or (2, 0)
two_sum([3, 2, 4], 6) # returns (1, 2) or (2, 1)

Solution

def two_sum(numbers, target):
    '''
    实现步骤：
        遍历数组：对于数组中的每一个元素，我们计算目标值与当前元素的差值。这个差值就是我们需要在数组中寻找的另一个元素。
        使用字典（哈希表）：在遍历数组的过程中，我们将已经遍历过的元素及其对应的索引存储在字典中。这样我们可以快速检查之前是否已经遇到过所需的差值。
        检查匹配对：如果当前元素所对应的差值已经在字典中存在，那么我们就找到了这两个元素，可以直接返回它们的索引。
    '''
    lookup = {}
    for i, num in enumerate(numbers):
        difference = target - num
        if difference in lookup:
            return (lookup[difference], i)
        lookup[num] = i

Sum of Paris

Description

https://www.codewars.com/kata/54d81488b981293527000c8f/

Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

If there are two or more pairs with the required sum, the pair whose second element has the smallest index is the solution.

sum_pairs([11, 3, 7, 5],         10)
#              ^--^      3 + 7 = 10
== [3, 7]

sum_pairs([4, 3, 2, 3, 4],         6)
#          ^-----^         4 + 2 = 6, indices: 0, 2 *
#             ^-----^      3 + 3 = 6, indices: 1, 3
#                ^-----^   2 + 4 = 6, indices: 2, 4
#  * the correct answer is the pair whose second value has the smallest index
== [4, 2]

sum_pairs([0, 0, -2, 3], 2)
#  there are no pairs of values that can be added to produce 2.
== None/nil/undefined (Based on the language)

sum_pairs([10, 5, 2, 3, 7, 5],         10)
#              ^-----------^   5 + 5 = 10, indices: 1, 5
#                    ^--^      3 + 7 = 10, indices: 3, 4 *
#  * the correct answer is the pair whose second value has the smallest index
== [3, 7]

Negative numbers and duplicate numbers can and will appear.

NOTE: There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn’t time out.

Solution

def sum_pairs(ints, s):
    '''
    hash-based approach
    1. Use a Set for Lookup: Create a set to keep track of the integers we've seen so far as we iterate through the list. 
    This allows us to quickly check if the complement of the current number (i.e., sum - current_number) is in the set.

    2. Iterate Through the List: For each number in the list, calculate its complement with respect to the target sum. 
    If the complement is already in the set, we've found a valid pair. If not, add the current number to the set and continue.

    3. Return the First Valid Pair: Once a valid pair is found, return it immediately. 
    If no pair is found after processing the entire list, return None.
    '''
    seen = set()
    
    for num in ints:
        target = s - num
        if target in seen:
            return [target, num]
        seen.add(num)
    
    return None

Stack and Queue

Directions Reduction

Description

https://www.codewars.com/kata/550f22f4d758534c1100025a/

Once upon a time, on a way through the old wild mountainous west,… … a man was given directions to go from one point to another. The directions were “NORTH”, “SOUTH”, “WEST”, “EAST”. Clearly “NORTH” and “SOUTH” are opposite, “WEST” and “EAST” too.

Going to one direction and coming back the opposite direction right away is a needless effort. Since this is the wild west, with dreadful weather and not much water, it’s important to save yourself some energy, otherwise you might die of thirst!

How I crossed a mountainous desert the smart way.

The directions given to the man are, for example, the following (depending on the language):

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"].
or
{ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" };
or
[North, South, South, East, West, North, West]

You can immediately see that going “NORTH” and immediately “SOUTH” is not reasonable, better stay to the same place! So the task is to give to the man a simplified version of the plan. A better plan in this case is simply:

["WEST"]
or
{ "WEST" }
or
[West]

Other examples:

In ["NORTH", "SOUTH", "EAST", "WEST"], the direction "NORTH" + "SOUTH" is going north and coming back right away.

The path becomes ["EAST", "WEST"], now "EAST" and "WEST" annihilate each other, therefore, the final result is [] (nil in Clojure).

In ["NORTH", "EAST", "WEST", "SOUTH", "WEST", "WEST"], "NORTH" and "SOUTH" are not directly opposite but they become directly opposite after the reduction of "EAST" and WEST" so the whole path is reducible to ["WEST", "WEST"].

Task Write a function dirReduc which will take an array of strings and returns an array of strings with the needless directions removed (W<->E or S<->N side by side).

The Haskell version takes a list of directions with data Direction = North | East | West | South.

The Clojure version returns nil when the path is reduced to nothing.

The Rust version takes a slice of enum Direction {North, East, West, South}.

See more examples in “Sample Tests:”

Notes

Not all paths can be made simpler. The path ["NORTH", "WEST", "SOUTH", "EAST"] is not reducible. "NORTH" and "WEST", "WEST" and "SOUTH", "SOUTH" and "EAST" are not directly opposite of each other and can’t become such. Hence the result path is itself : ["NORTH", "WEST", "SOUTH", "EAST"].

Solution

def dirReduc(directions):
    '''
    1. 初始化一个空的栈。
    2. 遍历给定的方向数组。
    3. 对于每个方向，检查栈顶元素：
        - 如果栈为空或者当前方向与栈顶方向不相反，则将当前方向压入栈中。
        - 如果当前方向与栈顶方向相反，则弹出栈顶元素（因为这两个方向抵消）。
    4. 遍历完成后，栈中剩下的方向即为简化后的路径。
    '''
    # 定义相反方向的映射
    opposite = {"NORTH": "SOUTH", "SOUTH": "NORTH", "EAST": "WEST", "WEST": "EAST"}
    stack = []
    
    for direction in directions:
        if stack and stack[-1] == opposite[direction]:
            # 如果当前方向与栈顶方向相反，弹出栈顶方向
            stack.pop()
        else:
            # 否则，将当前方向压入栈中
            stack.append(direction)
    
    return stack

The Supermarket Queue

Description

https://www.codewars.com/kata/57b06f90e298a7b53d000a86

There is a queue for the self-checkout tills at the supermarket. Your task is write a function to calculate the total time required for all the customers to check out!

input

• customers: an array of positive integers representing the queue. Each integer represents a customer, and its value is the amount of time they require to check out.
• n: a positive integer, the number of checkout tills.

output: The function should return an integer, the total time required.

Important: Please look at the examples and clarifications below, to ensure you understand the task correctly :)

Examples

queue_time([5,3,4], 1)
# should return 12
# because when n=1, the total time is just the sum of the times

queue_time([10,2,3,3], 2)
# should return 10
# because here n=2 and the 2nd, 3rd, and 4th people in the 
# queue finish before the 1st person has finished.

queue_time([2,3,10], 2)
# should return 12

Clarifications

• There is only ONE queue serving many tills, and
• The order of the queue NEVER changes, and
• The front person in the queue (i.e. the first element in the array/list) proceeds to a till as soon as it becomes free.

N.B. You should assume that all the test input will be valid, as specified above.

P.S. The situation in this kata can be likened to the more-computer-science-related idea of a thread pool, with relation to running multiple processes at the same time: https://en.wikipedia.org/wiki/Thread_pool

Solution

import heapq

def queue_time(customers, n):
    '''
    - Use a priority queue (or min-heap) to simulate the working status of the checkout tills.
    - Initialization: Create a priority queue of size n to represent the current total time at each checkout till.
    - Assignment: Distribute customers to the checkout tills in turn and update the total time for each till.
    - Result Calculation: The total time required for all customers to complete checkout is the maximum time among all checkout tills.
    '''

    if n == 0:
        return 0
    if len(customers) == 0:
        return 0

    tills = [0] * n
    for time in customers:
        # Remove the till with the minimum total time
        min_time = heapq.heappop(tills)
        # Add the customer's time to this till
        heapq.heappush(tills, min_time + time)

    # Return the maximum time among all tills
    return max(tills)

Algorithms

Dynamic programming

Expressions Matter

Description

https://www.codewars.com/kata/5ae62fcf252e66d44d00008e/python

Given three integers a, b, and c, return the largest number obtained after inserting the operators +, *, and parentheses (). In other words, try every combination of a, b, and c with the operators, without reordering the operands, and return the maximum value.

Example With the numbers 1, 2, and 3, here are some possible expressions:

• 1 * (2 + 3) = 5
• 1 * 2 * 3 = 6
• 1 + 2 * 3 = 7
• (1 + 2) * 3 = 9

The maximum value that can be obtained is 9.

Notes

• The numbers are always positive, in the range 1 ≤ a, b, c ≤ 10.
• You can use the same operation more than once.
• It is not necessary to use all the operators or parentheses.
• You cannot swap the operands. For example, with the given numbers, you cannot get the expression (1 + 3) * 2 = 8.

Input and Output Examples

• expressionsMatter(1, 2, 3) ==> 9, because (1 + 2) * 3 = 9.
• expressionsMatter(1, 1, 1) ==> 3, because 1 + 1 + 1 = 3.
• expressionsMatter(9, 1, 1) ==> 18, because 9 * (1 + 1) = 18.

Solution

def expression_matter(a, b, c):
    # Calculate all possible values with the given operators and parentheses
    result1 = a + b + c
    result2 = a + (b * c)
    result3 = (a + b) * c
    result4 = a * b * c
    result5 = a * (b + c)
    
    # Return the maximum value among all possible results
    return max(result1, result2, result3, result4, result5)

from itertools import permutations, product

def expressionsMatter(a, b, c):
    # Define all possible operations and parentheses combinations
    expressions = [
        lambda a, b, c: a + b + c,
        lambda a, b, c: a + (b * c),
        lambda a, b, c: (a + b) * c,
        lambda a, b, c: a * b * c,
        lambda a, b, c: a * (b + c)
    ]
    
    # Compute the results of all expressions
    results = [expr(a, b, c) for expr in expressions]
    
    # Return the maximum value
    return max(results)

# When dealing with larger datasets, especially with multiple variables, 
# brute force enumeration of all possible expressions becomes infeasible due to the rapidly increasing number of combinations. 
# For more complex problems, more efficient algorithms are required to compute the maximum value. 
# In such cases, dynamic programming is a suitable approach, 
# but it requires careful consideration of various details when handling more variables and operators.

import numpy as np

def max_expression(nums):
    '''
    1. Define the Problem: We need to define a DP table where dp[i][j] represents the maximum value of the subarray from index i to index j.
    2. Recursive and State Transition: For each subarray [i, j], 
        we solve the problem by splitting it into two parts. 
        We recursively solve the subproblems for the left and right parts and then combine their results to get the maximum value for the current subarray. 
        We need to consider all possible operators (+ and *) and parenthesis combinations.
    3. Fill the Table: Iterate through all possible subarray lengths and update the DP table accordingly.
    '''
    # Define operators
    def apply_op(op, x, y):
        if op == "+":
            return x + y
        elif op == "*":
            return x * y

    n = len(nums)
    if n == 0:
        return 0

    # Dynamic programming table
    dp = np.full((n, n), -float("inf"))

    # Base cases
    for i in range(n):
        dp[i][i] = nums[i]

    # Fill the table
    for length in range(2, n + 1):  # Length of subproblem
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                dp[i][j] = max(dp[i][j], apply_op("+", dp[i][k], dp[k + 1][j]))
                dp[i][j] = max(dp[i][j], apply_op("*", dp[i][k], dp[k + 1][j]))

    # Return the maximum value in the range [0, n-1]
    return dp[0][n - 1]


# Example test
print(max_expression([1, 2, 3, 4]))  # Example: (1 + 2) * 3 * 4 = 36

Complexity

Gap in Primes

Description

https://www.codewars.com/kata/561e9c843a2ef5a40c0000a4/python

The prime numbers are not regularly spaced. For example from 2 to 3 the gap is 1. From 3 to 5 the gap is 2. From 7 to 11 it is 4. Between 2 and 50 we have the following pairs of 2-gaps primes: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43

A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes (see: http://mathworld.wolfram.com/PrimeGaps.html).

We will write a function gap with parameters:

• g (integer >= 2) which indicates the gap we are looking for
• m (integer > 2) which gives the start of the search (m inclusive)
• n (integer >= m) which gives the end of the search (n inclusive)

In the example above gap(2, 3, 50) will return [3, 5] or (3, 5) or {3, 5} which is the first pair between 3 and 50 with a 2-gap.

So this function should return the first pair of two prime numbers spaced with a gap of g between the limits m, n if these numbers exist otherwise nil or null or Noneor Nothing (or…` depending on the language).

• In such a case (no pair of prime numbers with a gap of g)
• In C: return [0, 0]
• In C++, Lua, COBOL: return {0, 0}.
• In F#: return [||].
• In Kotlin, Dart and Prolog: return [].
• In Pascal: return Type TGap (0, 0).

Examples:

• gap(2, 5, 7) –> [5, 7] or (5, 7) or {5, 7}
• gap(2, 5, 5) –> nil. In C++ {0, 0}. In F# [||]. In Kotlin, Dart and Prolog return []`
• gap(4, 130, 200) –> [163, 167] or (163, 167) or {163, 167}

([193, 197] is also such a 4-gap primes between 130 and 200 but it’s not the first pair)

• gap(6,100,110) –> nil or {0, 0} or ... : between 100 and 110 we have 101, 103, 107, 109 but 101-107is not a 6-gap because there is 103 in between and 103-109 is not a 6-gap because there is 107 in between.
• You can see more examples of return in Sample Tests.

Note for Go: For Go: nil slice is expected when there are no gap between m and n. Example: gap(11,30000,100000) –> nil

Solution

# Time Complexity: The sieve algorithm runs in 𝑂(𝑛log⁡log𝑛) and filtering the primes is linear in terms of the number of primes found.
# Space Complexity: The space complexity is mainly for storing the prime numbers, which is efficient given that the sieve is optimized for this task.
def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    p = 2
    while (p * p <= limit):
        if (is_prime[p] == True):
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
        p += 1
    primes = [p for p in range(2, limit + 1) if is_prime[p]]
    return primes

def gap(g, m, n):
    # Generate all primes up to n
    primes = sieve_of_eratosthenes(n)
    
    # Filter primes to be within the range [m, n]
    primes_in_range = [p for p in primes if p >= m]
    
    # Find the first pair with gap g
    for i in range(len(primes_in_range) - 1):
        if primes_in_range[i+1] - primes_in_range[i] == g:
            return [primes_in_range[i], primes_in_range[i+1]]
    
    # If no such pair is found
    return None

# Examples
print(gap(2, 5, 7))      # Output: [5, 7]
print(gap(2, 5, 5))      # Output: None
print(gap(4, 130, 200))  # Output: [163, 167]
print(gap(6, 100, 110))  # Output: None

# Memory Efficiency: Instead of storing all primes up to n, we only store primes in the range [m, n], which reduces memory usage.
# Time Efficiency: The segmented sieve approach avoids redundant computations and limits operations to the relevant range, improving performance for large ranges.
import math

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    p = 2
    while p * p <= limit:
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
        p += 1
    primes = [p for p in range(2, limit + 1) if is_prime[p]]
    return primes

def segmented_sieve(m, n):
    limit = int(math.sqrt(n)) + 1
    primes = sieve_of_eratosthenes(limit)
    
    # Create a boolean array for the range [m, n]
    range_prime = [True] * (n - m + 1)
    
    for prime in primes:
        # Find the minimum number in the [m, n] range that is a multiple of `prime`
        start = max(prime * prime, m + (prime - m % prime) % prime)
        
        for j in range(start, n + 1, prime):
            range_prime[j - m] = False
    
    # Collect all primes in the range [m, n]
    range_primes = [i for i in range(m, n + 1) if range_prime[i - m] and (i >= 2)]
    
    return range_primes

def gap(g, m, n):
    if n < m:
        return None
    
    # Generate primes in the range [m, n]
    primes_in_range = segmented_sieve(m, n)
    
    # Find the first pair with gap g
    for i in range(len(primes_in_range) - 1):
        if primes_in_range[i + 1] - primes_in_range[i] == g:
            return [primes_in_range[i], primes_in_range[i + 1]]
    
    return None

# Examples
print(gap(2, 5, 7))      # Output: [5, 7]
print(gap(2, 5, 5))      # Output: None
print(gap(4, 130, 200))  # Output: [163, 167]
print(gap(6, 100, 110))  # Output: None