3115. Maximum Prime Difference

Posted on Edited on In

3115. Maximum Prime Difference

Description

You are given an integer array nums.

Return an integer that is the maximum distance between the indices of two (not necessarily different) prime numbers in nums.

Example 1:

1
2
3
4
5
Input: nums = [4,2,9,5,3]

Output: 3

Explanation: `nums[1]`, `nums[3]`, and `nums[4]` are prime. So the answer is `|4 - 1| = 3`.

Example 2:

1
2
3
4
5
Input: nums = [4,8,2,8]

Output: 0

Explanation: `nums[2]` is prime. Because there is just one prime number, the answer is `|2 - 2| = 0`.

Constraints:

  • 1 <= nums.length <= 3 * 10^5
  • 1 <= nums[i] <= 100
  • The input is generated such that the number of prime numbers in the nums is at least one.

Hints/Notes

  • two pointers, from beginning and end of the array

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    map<int, bool> prime;

    int maximumPrimeDifference(vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        prime[1] = false;
        prime[2] = true;
        while (low <= high) {
            bool isPrimeLow = primeNumber(nums[low]);
            bool isPrimeHigh = primeNumber(nums[high]);
            if (isPrimeLow && isPrimeHigh) {
                return high - low;
            }
            if (!isPrimeLow) {
                low++;
            }
            if (!isPrimeHigh) {
                high--;
            }
        }
        return 0;
    }

    bool primeNumber(int num) {
        if (prime.contains(num)) {
            return prime[num];
        }
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                prime[num] = false;
                return false;
            }
        }
        prime[num] = true;
        return true;
    }
};