[LeetCode] 2523. Closest Prime Numbers in Range

Problem

https://leetcode.com/problems/closest-prime-numbers-in-range/description/

Leetcode - Closest Prime Numbers in Range

Type - Math, Number Theory

Difficulty - Medium

Approach & Solution

Examine the sequences prime numbers.

To get the minimum gap, only comparing adjacent prime numbers is efficient.

data structure and variables:

• isPrime: Sieve of Eratosthenes - A boolean array.

• lastPrime: last encountered prime number.

• minGap: minimum gap between two adjacent pairs.

• ans: stores pair num1 and num2.

By maintaining lastPrime and updating minGap dynamically, we can efficiently determine the closest prime pair.

Complexity

Time Complexity: O(right log log right) - Sieve of Eratosthenes.

Space Complexity: O(right) - Sieve of Eratosthenes.

Code (C++ | Go)

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> closestPrimes(int left, int right) {
        vector<bool> isPrime(right+1, true);
        int lastPrime = INT_MIN;
        int minGap = INT_MAX;
        vector<int> ans = {-1, -1};

        isPrime[0] = false;
        isPrime[1] = false;
        for(int i = 2; i <= right; i++) {
            if(!isPrime[i]) continue;
            for(int j = i*2; j <= right; j += i) {
                isPrime[j] = false;
            }

            if(i >= left) {
                if(lastPrime > 0) {
                    if(i - lastPrime < minGap) {
                        minGap = i - lastPrime;
                        ans = {lastPrime, i};
                    } 
                }
                lastPrime = i;
            }
        }

        return ans;
    }
};

func closestPrimes(left int, right int) []int {
    isPrime := make([]bool, right+1)
    minGap := math.MaxInt
    lastPrime := -1
    ans := []int{-1, -1}
    for i := 2; i <= right; i++ {
        isPrime[i] = true
    }

    for i := 2; i <= right; i++ {
        if !isPrime[i] {
            continue
        }

        for j := i*2; j <= right; j += i {
            isPrime[j] = false
        }

        if i >= left {
            if lastPrime > 0 {
                if i - lastPrime < minGap {
                    minGap = i - lastPrime
                    ans[0] = lastPrime
                    ans[1] = i
                }
            }
            lastPrime = i
        }
    }

    return ans
}