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:
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:
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 * 105
1 <= nums[i] <= 100
- The input is generated such that the number of prime numbers in the
nums
is at least one.
Solutions
Solution 1: Traversal
According to the problem description, we need to find the index $i$ of the first prime number, then find the index $j$ of the last prime number, and return $j - i$ as the answer.
Therefore, we can traverse the array from left to right to find the index $i$ of the first prime number, then traverse the array from right to left to find the index $j$ of the last prime number. The answer is $j - i$.
The time complexity is $O(n \times \sqrt{M})$, where $n$ and $M$ are the length of the array $nums$ and the maximum value in the array, respectively. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
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 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|