Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 7

Description

Closest Prime Numbers in Range

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 <= 106

Solution

class Solution {
  bool isPrime(int n) {
    if(n < 2) return false;
    for(int i = 2; i * i <= n; ++i) {
      if(!(n % i)) return false;
    }
    return true;
  }
public:
  vector<int> closestPrimes(int left, int right) {
    int prev = -1;
    int diff = 1e7;
    vector<int> answer{-1, -1};
    for(int i = left; i <= right; ++i) {
      if(!isPrime(i)) continue;
      if(prev == -1) {
        prev = i;
      } else {
        if(i - prev < diff) {
          diff = i - prev;
          answer[0] = prev;
          answer[1] = i;
        }
        if(diff < 3) break;
        prev = i;
      }
    }
    return answer;
  }
};

// Accepted
// 66/66 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 96.48 % of cpp submissions (8.1 MB)