Jobs

Interviews

Discussions

Closest Prime Numbers in Range

Medium

Asked by:

More companies

22 views

Topics:

ArraysTwo Pointers

Given two positive integers left and right, find the two integers num1 and num2 such that:

left <= num1 < num2 <= right .
Both num1 and num2 are prime numbers.
num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Return the positive integer array ans = [num1, num2]. If there are multiple pairs satisfying these conditions, return the one with the smallest num1 value. If no such numbers exist, return [-1, -1].

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

1 <= left <= right <= 10⁶

Try coding it in LeetCode

Closest Prime Numbers in Range

Medium

Asked by:

22 views

Topics:

ArraysTwo Pointers

Given two positive integers left and right, find the two integers num1 and num2 such that:

left <= num1 < num2 <= right .
Both num1 and num2 are prime numbers.
num2 - num1 is the minimum amongst all other pairs satisfying the above conditions.

Example 1:

Input: left = 10, right = 19
Output: [11,13]
Explanation: The prime numbers between 10 and 19 are 11, 13, 17, and 19.
The closest gap between any pair is 2, which can be achieved by [11,13] or [17,19].
Since 11 is smaller than 17, we return the first pair.

Example 2:

Input: left = 4, right = 6
Output: [-1,-1]
Explanation: There exists only one prime number in the given range, so the conditions cannot be satisfied.

Constraints:

1 <= left <= right <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper and lower bounds for the input range left and right?
What should I return if there are no prime numbers within the given range, or if there is only one prime number?
Are `left` and `right` inclusive or exclusive bounds?
Are `left` and `right` guaranteed to be positive integers?
How should I handle the case where `left` is greater than `right`?

Brute Force Solution

Approach

We're looking for two prime numbers within a specified range that are as close to each other as possible. The brute force method checks every single pair of numbers in that range to see if they are prime and calculates their distance.

Here's how the algorithm would work step-by-step:

Start with the first number in the range.
Check if that number is a prime number. A number is prime if it is only divisible by 1 and itself.
If the first number is prime, go through every other number in the range starting from the next number.
For each of these other numbers, check if it is a prime number.
If both numbers are prime, calculate the distance between them.
Keep track of the smallest distance found so far, and the pair of prime numbers that created that distance.
Continue checking all possible pairs of numbers in the range in this way.
Once all pairs have been checked, the pair with the smallest distance is the answer.

Code Implementation

def closest_prime_numbers(left, right):    closest_primes = None
    min_distance = float('inf')

    def is_prime(number_to_check):
        if number_to_check <= 1:
            return False
        for i in range(2, int(number_to_check**0.5) + 1):
            if number_to_check % i == 0:
                return False
        return True

    for first_number in range(left, right + 1):

        # Optimization: Skip non-prime numbers to improve performance
        if not is_prime(first_number):
            continue

        for second_number in range(first_number + 1, right + 1):

            # Optimization: Skip non-prime numbers to improve performance
            if not is_prime(second_number):
                continue

            distance = second_number - first_number

            # Update closest primes if current distance is smaller
            if distance < min_distance:
                min_distance = distance
                closest_primes = [first_number, second_number]

    # Returning none when no primes are found
    return closest_primes

Big(O) Analysis

Time Complexity

O(n² * sqrt(n)) – The outer loop iterates through approximately n numbers within the given range. Inside the outer loop, the inner loop also iterates through approximately n numbers to check all possible pairs. For each number within the nested loops, we perform a primality test. A naive primality test involves checking divisibility from 2 up to the square root of the number, contributing a factor of sqrt(n) to the time complexity for each prime check. Therefore, the total time complexity can be approximated as O(n * n * sqrt(n)) or O(n² * sqrt(n)).

Space Complexity

O(1) – The provided algorithm iterates through pairs within the given range, keeping track of the closest prime numbers found so far and their distance. It stores the smallest distance found (a single number), and the pair of prime numbers that produced that distance (two numbers). The amount of extra memory needed to store these three numbers (smallest distance and the two prime numbers) does not depend on the size of the input range (N). Therefore, the space complexity is constant.

Optimal Solution

Approach

To find the closest prime numbers within a range efficiently, we first identify all prime numbers in that range. Then, we simply find the pair of prime numbers that are closest to each other.

Here's how the algorithm would work step-by-step:

First, create a list of all numbers within the given range.
Next, mark all the numbers in the list as potentially prime.
Starting with the smallest prime number, 2, eliminate all of its multiples from the list.
Move to the next unmarked number in the list; this is the next prime number. Eliminate all of its multiples.
Repeat the process of finding the next unmarked number and eliminating its multiples until you reach the square root of the upper bound of the range. At this point, all remaining unmarked numbers in the list are prime.
Now that you have a list of all prime numbers within the range, iterate through the list, keeping track of the smallest difference between adjacent prime numbers that you find.
Return the pair of prime numbers that produce this smallest difference.

Code Implementation

def closest_prime_numbers(left_bound, right_bound):
    number_range = list(range(left_bound, right_bound + 1))
    is_prime = [True] * len(number_range)

    # 0 and 1 are not prime
    if left_bound <= 1:
        is_prime[max(0, 1 - left_bound)] = False
    if left_bound <= 0:
        is_prime[max(0, 0 - left_bound)] = False

    for number in range(2, int(right_bound**0.5) + 1):
        # Optimization: skip if already marked non-prime
        if number >= left_bound and not is_prime[number - left_bound]:
            continue

        # Eliminating multiples of the current prime number
        start = max(number * number, ((left_bound + number - 1) // number) * number)
        for multiple in range(start, right_bound + 1, number):
            is_prime[multiple - left_bound] = False

    prime_numbers = []
    for index, value in enumerate(is_prime):
        if value:
            prime_numbers.append(number_range[index])

    if len(prime_numbers) < 2:
        return None

    min_difference = float('inf')
    closest_primes = None

    # Find the pair of primes with the minimum difference
    for i in range(len(prime_numbers) - 1):
        difference = prime_numbers[i+1] - prime_numbers[i]

        # Keeping track of minimum difference between primes
        if difference < min_difference:
            min_difference = difference
            closest_primes = [prime_numbers[i], prime_numbers[i+1]]

    return closest_primes

Big(O) Analysis

Time Complexity

O(n log log n) – Generating primes using the Sieve of Eratosthenes within a range of size n (where n is upper - lower + 1) involves iterating through the numbers up to the square root of the range's upper bound and marking multiples. The number of operations for sieving is approximately n log log n. Finding the closest pair then involves iterating through the generated primes, which takes O(n) time in the worst case, since at most all numbers in the range are primes. The overall complexity is dominated by the sieve, resulting in O(n log log n).

Space Complexity

O(N) – The algorithm creates a list of all numbers within the given range, which requires space proportional to the range size N. This list is used to mark numbers as potentially prime and eliminate multiples. After sieving, a list of primes is implicitly generated within the initial array and accessed sequentially. Therefore, the auxiliary space used is dominated by the 'potentially prime' list of size N, giving a space complexity of O(N).

Edge Cases

Case	How to Handle
Invalid input range (left > right)	Return an empty list or null if the input range is invalid, indicating no valid primes.
Range contains no prime numbers	Return an empty list or null if no prime numbers exist within the range to indicate that no closest pair can be found.
Input range includes negative numbers	Since prime numbers are defined for positive integers, only consider the positive portion of the range or return an empty list if the entire range is negative.
Large input range causing potential integer overflow during calculations (e.g., in sieve)	Use a data type that supports larger numbers, like long, to avoid integer overflow issues.
Range starts or ends with a prime number	The algorithm should correctly identify and consider these boundary prime numbers when searching for the closest pair.
Small range with only one prime number	Return null or an empty list as no pair can be formed if there's only one prime number.
left and right are equal and prime	Return null or an empty list as no pair can be formed if left and right are equal, there is only one prime number
left and right are large non-primes that are close to primes	The primality test must efficiently handle near-prime numbers without excessive computation, so a sieve or optimized primality test is important.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper and lower bounds for the input range left and right?
What should I return if there are no prime numbers within the given range, or if there is only one prime number?
Are `left` and `right` inclusive or exclusive bounds?
Are `left` and `right` guaranteed to be positive integers?
How should I handle the case where `left` is greater than `right`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the range.
Check if that number is a prime number. A number is prime if it is only divisible by 1 and itself.
If the first number is prime, go through every other number in the range starting from the next number.
For each of these other numbers, check if it is a prime number.
If both numbers are prime, calculate the distance between them.
Keep track of the smallest distance found so far, and the pair of prime numbers that created that distance.
Continue checking all possible pairs of numbers in the range in this way.
Once all pairs have been checked, the pair with the smallest distance is the answer.

Code Implementation

def closest_prime_numbers(left, right):    closest_primes = None
    min_distance = float('inf')

    def is_prime(number_to_check):
        if number_to_check <= 1:
            return False
        for i in range(2, int(number_to_check**0.5) + 1):
            if number_to_check % i == 0:
                return False
        return True

    for first_number in range(left, right + 1):

        # Optimization: Skip non-prime numbers to improve performance
        if not is_prime(first_number):
            continue

        for second_number in range(first_number + 1, right + 1):

            # Optimization: Skip non-prime numbers to improve performance
            if not is_prime(second_number):
                continue

            distance = second_number - first_number

            # Update closest primes if current distance is smaller
            if distance < min_distance:
                min_distance = distance
                closest_primes = [first_number, second_number]

    # Returning none when no primes are found
    return closest_primes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To find the closest prime numbers within a range efficiently, we first identify all prime numbers in that range. Then, we simply find the pair of prime numbers that are closest to each other.

Here's how the algorithm would work step-by-step:

First, create a list of all numbers within the given range.
Next, mark all the numbers in the list as potentially prime.
Starting with the smallest prime number, 2, eliminate all of its multiples from the list.
Move to the next unmarked number in the list; this is the next prime number. Eliminate all of its multiples.
Repeat the process of finding the next unmarked number and eliminating its multiples until you reach the square root of the upper bound of the range. At this point, all remaining unmarked numbers in the list are prime.
Now that you have a list of all prime numbers within the range, iterate through the list, keeping track of the smallest difference between adjacent prime numbers that you find.
Return the pair of prime numbers that produce this smallest difference.

Code Implementation

def closest_prime_numbers(left_bound, right_bound):
    number_range = list(range(left_bound, right_bound + 1))
    is_prime = [True] * len(number_range)

    # 0 and 1 are not prime
    if left_bound <= 1:
        is_prime[max(0, 1 - left_bound)] = False
    if left_bound <= 0:
        is_prime[max(0, 0 - left_bound)] = False

    for number in range(2, int(right_bound**0.5) + 1):
        # Optimization: skip if already marked non-prime
        if number >= left_bound and not is_prime[number - left_bound]:
            continue

        # Eliminating multiples of the current prime number
        start = max(number * number, ((left_bound + number - 1) // number) * number)
        for multiple in range(start, right_bound + 1, number):
            is_prime[multiple - left_bound] = False

    prime_numbers = []
    for index, value in enumerate(is_prime):
        if value:
            prime_numbers.append(number_range[index])

    if len(prime_numbers) < 2:
        return None

    min_difference = float('inf')
    closest_primes = None

    # Find the pair of primes with the minimum difference
    for i in range(len(prime_numbers) - 1):
        difference = prime_numbers[i+1] - prime_numbers[i]

        # Keeping track of minimum difference between primes
        if difference < min_difference:
            min_difference = difference
            closest_primes = [prime_numbers[i], prime_numbers[i+1]]

    return closest_primes

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Invalid input range (left > right)	Return an empty list or null if the input range is invalid, indicating no valid primes.
Range contains no prime numbers	Return an empty list or null if no prime numbers exist within the range to indicate that no closest pair can be found.
Input range includes negative numbers	Since prime numbers are defined for positive integers, only consider the positive portion of the range or return an empty list if the entire range is negative.
Large input range causing potential integer overflow during calculations (e.g., in sieve)	Use a data type that supports larger numbers, like long, to avoid integer overflow issues.
Range starts or ends with a prime number	The algorithm should correctly identify and consider these boundary prime numbers when searching for the closest pair.
Small range with only one prime number	Return null or an empty list as no pair can be formed if there's only one prime number.
left and right are equal and prime	Return null or an empty list as no pair can be formed if left and right are equal, there is only one prime number
left and right are large non-primes that are close to primes	The primality test must efficiently handle near-prime numbers without excessive computation, so a sieve or optimized primality test is important.