3589. Count Prime-Gap Balanced Subarrays
You are given an integer array nums and an integer k.
A subarray is called prime-gap balanced if:
- It contains at least two prime numbers, and
- The difference between the maximum and minimum prime numbers in that subarray is less than or equal to
k.
Return the count of prime-gap balanced subarrays in nums.
Note:
- A subarray is a contiguous non-empty sequence of elements within an array.
- A prime number is a natural number greater than 1 with only two factors, 1 and itself.
Example 1:
Input: nums = [1,2,3], k = 1
Output: 2
Explanation:
Prime-gap balanced subarrays are:
[2,3]: contains two primes (2 and 3), max - min =3 - 2 = 1 <= k.[1,2,3]: contains two primes (2 and 3), max - min =3 - 2 = 1 <= k.
Thus, the answer is 2.
Example 2:
Input: nums = [2,3,5,7], k = 3
Output: 4
Explanation:
Prime-gap balanced subarrays are:
[2,3]: contains two primes (2 and 3), max - min =3 - 2 = 1 <= k.[2,3,5]: contains three primes (2, 3, and 5), max - min =5 - 2 = 3 <= k.[3,5]: contains two primes (3 and 5), max - min =5 - 3 = 2 <= k.[5,7]: contains two primes (5 and 7), max - min =7 - 5 = 2 <= k.
Thus, the answer is 4.
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 5 * 1040 <= k <= 5 * 104
ArrayMathQueueSliding WindowNumber TheoryMonotonic Queue
Hints
Hint 1
Sieve and extract primes.
Hint 2
Build a sparse-table for
O(1) max–min queries.Hint 3
For each prime, binary‐search the furthest valid partner.
Hint 4
Count subarrays via left/right gap multiplication.
Preparing judge…