Closest Prime Numbers in Range
MedPrompt
Given two positive integers left and right, find the two integers num1 and num2 such that:
left <= num1 < num2 <= right.- Both
num1andnum2are prime numbers. num2 - num1is 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 <= 106
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through every number in the given range [left, right]. For each number, we perform a primality test. The numbers that are identified as prime are stored in a list. Finally, we iterate through the list of found primes to find the pair with the minimum difference.
Algorithm
- Create a helper function
isPrime(n)that checks if a numbernis prime using trial division. This involves checking for divisibility by numbers from 2 up tosqrt(n). - Initialize an empty list,
primesInRange, to store the prime numbers found. - Iterate through each number
ifromlefttoright. - If
isPrime(i)returns true, addito theprimesInRangelist. - After the loop, check if
primesInRangecontains at least two numbers. If not, return[-1, -1]as no valid pair exists. - Initialize
minDiffto infinity and an answer arrayansto[-1, -1]. - Iterate through the
primesInRangelist from the first to the second-to-last element. - For each adjacent pair of primes
(p1, p2), calculate the differencediff = p2 - p1. - If
diffis less thanminDiff, updateminDifftodiffandansto[p1, p2]. - After checking all adjacent pairs, return the
ansarray.
Walkthrough
The core of this method is a helper function, isPrime(n), which determines if a number n is prime. This is done using trial division: we check if n is divisible by any integer from 2 up to its square root. If a divisor is found, n is not prime.
The main logic first builds a list of all prime numbers within [left, right] by calling isPrime() on each number. Once this list is populated, if it contains fewer than two primes, no such pair exists, and we return [-1, -1]. Otherwise, we iterate through the sorted list of primes, comparing each adjacent pair (p1, p2) and keeping track of the pair with the smallest difference p2 - p1. The first pair found with the minimum difference is the answer, as the list is sorted, satisfying the tie-breaking rule.
class Solution { // Helper function to check for primality using trial division private 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; } public int[] closestPrimes(int left, int right) { java.util.List<Integer> primes = new java.util.ArrayList<>(); for (int i = left; i <= right; i++) { if (isPrime(i)) { primes.add(i); } } if (primes.size() < 2) { return new int[]{-1, -1}; } int minDiff = Integer.MAX_VALUE; int[] result = new int[]{-1, -1}; for (int i = 0; i < primes.size() - 1; i++) { int diff = primes.get(i + 1) - primes.get(i); if (diff < minDiff) { minDiff = diff; result[0] = primes.get(i); result[1] = primes.get(i + 1); } } return result; }}Complexity
Time
O((right - left) * sqrt(right)). For each number in the range of size `N = right - left + 1`, we perform a primality test that takes up to `O(sqrt(right))` time. This is too slow for the given constraints.
Space
O(P), where P is the number of primes in the range `[left, right]`. In the worst case, this is approximately `O((right-left)/log(right))`. The space is used to store the list of prime numbers.
Trade-offs
Pros
Conceptually simple and easy to implement.
Requires minimal extra space, only for storing the primes found in the range.
Cons
The time complexity is very high, making it impractical for the given constraints (
rightup to 10^6).It will likely result in a 'Time Limit Exceeded' error on most online judges.
Solutions
Solution
class Solution {public int[] closestPrimes(int left, int right) { int cnt = 0; boolean[] st = new boolean[right + 1]; int[] prime = new int[right + 1]; for (int i = 2; i <= right; ++i) { if (!st[i]) { prime[cnt++] = i; } for (int j = 0; prime[j] <= right / i; ++j) { st[prime[j] * i] = true; if (i % prime[j] == 0) { break; } } } int i = -1, j = -1; for (int k = 0; k < cnt; ++k) { if (prime[k] >= left && prime[k] <= right) { if (i == -1) { i = k; } j = k; } } int[] ans = new int[]{-1, -1}; if (i == j || i == -1) { return ans; } int mi = 1 << 30; for (int k = i; k < j; ++k) { int d = prime[k + 1] - prime[k]; if (d < mi) { mi = d; ans[0] = prime[k]; ans[1] = prime[k + 1]; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.