Welcome to Subscribe On Youtube
3896. Minimum Operations to Transform Array into Alternating Prime
Description
You are given an integer array nums.
An array is considered alternating prime if:
- Elements at even indices (0-based) are prime numbers.
- Elements at odd indices are non-prime numbers.
In one operation, you may increment any element by 1.
Return the minimum number of operations required to transform nums into an alternating prime 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,4]
Output: 3
Explanation:
- The element at index 0 must be prime. Increment
nums[0] = 1to 2, using 1 operation. - The element at index 1 must be non-prime. Increment
nums[1] = 2to 4, using 2 operations. - The element at index 2 is already prime.
- The element at index 3 is already non-prime.
Total operations = 1 + 2 = 3.
Example 2:
Input: nums = [5,6,7,8]
Output: 0
Explanation:
- The elements at indices 0 and 2 are already prime.
- The elements at indices 1 and 3 are already non-prime.
No operations are needed.
Example 3:
Input: nums = [4,4]
Output: 1
Explanation:
- The element at index 0 must be prime. Increment
nums[0] = 4to 5, using 1 operation. - The element at index 1 is already non-prime.
Total operations = 1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
Solutions
Solution 1: Preprocessing + Binary Search
We can first preprocess a sufficiently large list of prime numbers, denoted as $\textit{primes}$, and a boolean array $\textit{isPrime}$, where $\textit{isPrime}[i]$ indicates whether $i$ is a prime number.
Then we traverse each element in the array:
- If the index of the current element is even, we need to increase it to the next prime number. We can use binary search on $\textit{primes}$ to find the first prime number greater than or equal to the current element, and add the difference between them to the answer.
- If the index of the current element is odd and the current element is prime, we need to increase it to the next non-prime number. For the prime number 2, we need 2 increments to reach the next non-prime number 4; for other prime numbers, we only need 1 increment to reach the next non-prime number.
Finally, return the answer.
The time complexity is $O(n \times \log P)$, and the space complexity is $O(P)$. Here, $n$ and $P$ are the length of the array and the length of the preprocessed prime list, respectively.
-
class Solution { private static final int MX = 200000; private static final boolean[] IS_PRIME = new boolean[MX + 1]; private static final List<Integer> PRIMES = new ArrayList<>(); static { Arrays.fill(IS_PRIME, true); IS_PRIME[0] = false; IS_PRIME[1] = false; for (int i = 2; i <= MX / i; ++i) { if (IS_PRIME[i]) { for (int j = i * i; j <= MX; j += i) { IS_PRIME[j] = false; } } } for (int i = 2; i <= MX; ++i) { if (IS_PRIME[i]) { PRIMES.add(i); } } } public int minOperations(int[] nums) { int ans = 0; for (int i = 0; i < nums.length; ++i) { int x = nums[i]; if ((i & 1) == 0) { int j = Collections.binarySearch(PRIMES, x); if (j < 0) { j = -j - 1; } ans += PRIMES.get(j) - x; } else if (IS_PRIME[x]) { ans += x == 2 ? 2 : 1; } } return ans; } } -
class Solution { public: int minOperations(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++i) { int x = nums[i]; if ((i & 1) == 0) { auto it = lower_bound(primes.begin(), primes.end(), x); ans += *it - x; } else if (isPrime[x]) { ans += x == 2 ? 2 : 1; } } return ans; } private: static constexpr int MX = 200000; inline static vector<bool> isPrime = [] { vector<bool> p(MX + 1, true); p[0] = p[1] = false; for (int i = 2; i <= MX / i; ++i) { if (p[i]) { for (int j = i * i; j <= MX; j += i) { p[j] = false; } } } return p; }(); inline static vector<int> primes = [] { vector<int> res; for (int i = 2; i <= MX; ++i) { if (isPrime[i]) { res.push_back(i); } } return res; }(); }; -
MX = 200000 is_prime = [True] * (MX + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(MX**0.5) + 1): if is_prime[i]: for j in range(i * i, MX + 1, i): is_prime[j] = False primes = [i for i in range(2, MX + 1) if is_prime[i]] class Solution: def minOperations(self, nums: list[int]) -> int: ans = 0 for i, x in enumerate(nums): if i % 2 == 0: j = bisect_left(primes, x) ans += primes[j] - x else: if is_prime[x]: ans += 2 if x == 2 else 1 return ans -
const MX = 200000 var isPrime = func() []bool { p := make([]bool, MX+1) for i := range p { p[i] = true } p[0], p[1] = false, false for i := 2; i <= MX/i; i++ { if p[i] { for j := i * i; j <= MX; j += i { p[j] = false } } } return p }() var primes = func() []int { var res []int for i := 2; i <= MX; i++ { if isPrime[i] { res = append(res, i) } } return res }() func minOperations(nums []int) (ans int) { for i, x := range nums { if i%2 == 0 { j := sort.SearchInts(primes, x) ans += primes[j] - x } else if isPrime[x] { if x == 2 { ans += 2 } else { ans++ } } } return } -
const MX = 200000; const isPrime: boolean[] = (() => { const p = Array<boolean>(MX + 1).fill(true); p[0] = p[1] = false; for (let i = 2; i <= Math.floor(MX / i); ++i) { if (p[i]) { for (let j = i * i; j <= MX; j += i) { p[j] = false; } } } return p; })(); const primes: number[] = Array.from({ length: MX - 1 }, (_, i) => i + 2).filter(i => isPrime[i]); function minOperations(nums: number[]): number { let ans = 0; for (let i = 0; i < nums.length; ++i) { const x = nums[i]; if ((i & 1) === 0) { const j = _.sortedIndex(primes, x); ans += primes[j] - x; } else if (isPrime[x]) { ans += x === 2 ? 2 : 1; } } return ans; }