2610. Closest Prime Numbers In Range¶

Difficulty: Medium

2610. Closest Prime Numbers in Range

Medium

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⁶

Solution¶

class Solution {
    public int[] closestPrimes(int left, int right) {
        int[] arr=new int[2];
        arr[0]=-1;
        arr[1]=-1;
        ArrayList<Integer> ans=new ArrayList<>();
        for(int i=left;i<=right;i++){
            if (isprime(i)) ans.add(i);
        }
        int len=ans.size();
        int min=Integer.MAX_VALUE;
        for(int i=0;i<len-1;i++){
            int x=Math.abs(ans.get(i)-ans.get(i+1));
            min=Math.min(min,x);
        }
        for(int i=0;i<len-1;i++){
            if(Math.abs(ans.get(i)-ans.get(i+1))==min){
                arr[0]=ans.get(i);
                arr[1]=ans.get(i+1);
                break;
            }
        }
        return arr;
    }
    public static boolean isprime(int n){
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here