Leetcode 2523: Closest Prime Numbers in Range
Given two integers
left and right, find the two prime numbers num1 and num2 such that: left <= num1 < num2 <= right, both are prime numbers, and the difference num2 - num1 is the smallest among all valid pairs. If multiple pairs have the same smallest difference, return the pair with the smallest num1. If no such pair exists, return [-1, -1].Problem
Approach
Steps
Complexity
Input: You are given two integers `left` and `right`. Find the pair of prime numbers `num1` and `num2` where `left <= num1 < num2 <= right`.
Example: left = 15, right = 30
Constraints:
• 1 <= left <= right <= 10^6
Output: Return the pair `[num1, num2]` where `num1` and `num2` are prime numbers and the difference `num2 - num1` is the smallest. If no such pair exists, return `[-1, -1]`.
Example: Output: [17, 19]
Constraints:
• The output must be a list of two integers representing the prime numbers, or [-1, -1] if no such pair exists.
Goal: Find the pair of prime numbers `num1` and `num2` such that the difference between them is minimized, while satisfying the constraints.
Steps:
• Generate all prime numbers up to the value of `right` using the Sieve of Eratosthenes.
• Find all prime numbers between `left` and `right`.
• Iterate through the primes to find the pair with the smallest difference.
Goal: The range `[left, right]` is such that `1 <= left <= right <= 10^6`.
Steps:
• The time complexity should be efficient enough to handle input up to 10^6.
Assumptions:
• The input values `left` and `right` are within the given constraints.
• Input: left = 15, right = 30
• Explanation: The prime numbers between 15 and 30 are [17, 19, 23, 29]. The smallest difference is 2, which occurs between 17 and 19.
• Input: left = 50, right = 60
• Explanation: The prime numbers between 50 and 60 are [53, 59], with a difference of 6.
• Input: left = 8, right = 10
• Explanation: There are no prime numbers between 8 and 10, so the output is `[-1, -1]`.
Approach: We can solve this problem by generating prime numbers up to `right` using the Sieve of Eratosthenes, then finding the pair of primes within the range `[left, right]` with the smallest difference.
Observations:
• We need to efficiently find prime numbers within a given range.
• The Sieve of Eratosthenes is a good approach to generate prime numbers efficiently up to `right`.
Steps:
• Use the Sieve of Eratosthenes to find all primes up to `right`.
• Identify primes in the range `[left, right]`.
• Find the pair of primes with the smallest difference and return them.
Empty Inputs:
• There are no cases with empty inputs since `left` and `right` are always positive integers.
Large Inputs:
• The algorithm should be efficient enough to handle inputs where `right` can be as large as 10^6.
Special Values:
• If there are no primes between `left` and `right`, return `[-1, -1]`.
Constraints:
• The solution must handle input ranges efficiently using the Sieve of Eratosthenes.
bool seive[1000001] = {};
vector<int> p = {2};
vector<int> closestPrimes(int left, int right) {
for(int i = 3; i < 1000001; i += 2) {
if(!seive[i]) {
p.push_back(i);
for (long long j = (long long) i * i; j < 1000001; j += i) {
seive[j] = true;
}
}
}
int n1 = -1, n2 = -1, i = lower_bound(p.begin(), p.end(), left) - p.begin();
for(; i + 1 < p.size() && p[i + 1] <= right; i++) {
if(n1 == -1 || n2 - n1 > p[i + 1] - p[i]) {
n1 = p[i];
n2 = p[i + 1];
if(n2 - n1 < 3) break;
}
}
return {n1, n2};
}
1 : Variable Initialization
bool seive[1000001] = {};
This initializes a sieve array to mark non-prime numbers. The array size is 1000001, which is large enough for the range we're dealing with.
2 : Vector Initialization
vector<int> p = {2};
This initializes a vector 'p' with the first prime number (2) to start the prime search.
3 : Function Definition
vector<int> closestPrimes(int left, int right) {
This defines the function 'closestPrimes' which takes two integers, 'left' and 'right', representing the range in which to find the closest primes.
4 : Prime Sieve Loop
for(int i = 3; i < 1000001; i += 2) {
This loop iterates over odd numbers starting from 3 up to 1000001 to find primes. Even numbers (except 2) are skipped.
5 : Prime Check
if(!seive[i]) {
This checks if 'i' is a prime number by verifying if it has been marked as non-prime in the sieve.
6 : Prime Addition
p.push_back(i);
If 'i' is a prime, it is added to the vector 'p' of prime numbers.
7 : Sieve Update
for (long long j = (long long) i * i; j < 1000001; j += i) {
This inner loop marks all multiples of 'i' as non-prime in the sieve, starting from 'i*i' to optimize the sieve process.
8 : Mark Non-Primes
seive[j] = true;
This marks 'j' as a non-prime number in the sieve.
9 : Variable Initialization
int n1 = -1, n2 = -1, i = lower_bound(p.begin(), p.end(), left) - p.begin();
This initializes variables 'n1' and 'n2' to store the closest primes, and 'i' to find the first prime number greater than or equal to 'left' using binary search.
10 : Prime Pair Search
for(; i + 1 < p.size() && p[i + 1] <= right; i++) {
This loop iterates through the vector of primes, starting from the first prime greater than or equal to 'left', and checks if the next prime is within the range 'right'.
11 : Update Closest Primes
if(n1 == -1 || n2 - n1 > p[i + 1] - p[i]) {
This condition checks if the current pair of primes has a smaller difference than the previously found pair. If so, it updates 'n1' and 'n2'.
12 : Assign Closest Primes
n1 = p[i];
This assigns the current prime to 'n1'.
13 : Assign Closest Primes
n2 = p[i + 1];
This assigns the next prime to 'n2'.
14 : Early Termination
if(n2 - n1 < 3) break;
If the difference between 'n2' and 'n1' is less than 3, the loop breaks as no closer primes can be found.
15 : Return Result
return {n1, n2};
This returns a vector containing the two closest primes 'n1' and 'n2'.
Best Case: O(n log log n)
Average Case: O(n log log n)
Worst Case: O(n log log n)
Description: The time complexity is dominated by the Sieve of Eratosthenes, which runs in O(n log log n).
Best Case: O(n)
Worst Case: O(n)
Description: Space complexity is O(n) due to storing prime numbers up to `right`.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus