3896. Minimum Operations to Transform Array into Alternating Prime

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

An array is considered alternating prime if it satisfies the following two conditions:

Elements located at even indices (using 0-based indexing) must be prime numbers.
Elements located at odd indices must be non-prime numbers.

You are allowed to perform an operation any number of times. In one operation, you may pick any element of the array and increment it by 1.

Your task is to return the minimum number of operations required to transform nums into an alternating prime array.

For reference, a prime number is a natural number greater than 1 whose only two factors are 1 and itself.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Making the locally optimal choice at each step produces the globally optimal result.

Open in Flowchart

Intuition

The key observation is that each element in the array can be handled independently. Since the only operation available is incrementing an element by 1, and incrementing one element never affects another, we can compute the cost for each position separately and simply add them all up.

For every element, what we need depends entirely on whether its index is even or odd:

Even index (must become prime): Since we can only increase a value, the cheapest way to make nums[i] prime is to raise it to the smallest prime number that is greater than or equal to nums[i]. The cost is the difference between that prime and the original value. If the element is already prime, the cost is 0 because the smallest prime ≥ nums[i] is itself.
Odd index (must become non-prime): If nums[i] is already non-prime, we do nothing, so the cost is 0. If it is prime, we must increase it until it becomes non-prime. For most primes p, the very next number p + 1 is even and therefore non-prime, so a single increment (cost 1) is enough. The only exception is 2: the next number 3 is also prime, so we must go all the way to 4, costing 2 operations.

To make these checks fast, we can preprocess prime information ahead of time. Using a sieve, we build a boolean array is_prime that tells us instantly whether any number is prime, and a sorted list primes of all prime numbers up to a sufficiently large limit.

With this preprocessing in place:

For even indices, finding the smallest prime ≥ nums[i] becomes a quick binary search over the sorted primes list.
For odd indices, checking whether nums[i] is prime is a direct is_prime lookup, and the special case of 2 is handled separately.

Summing these per-position costs gives the minimum total number of operations.

Solution Approach

Solution 1: Preprocessing + Binary Search

We first preprocess a sufficiently large amount of prime information. We choose an upper bound MX = 200000, which is large enough to cover the next prime above any value we might encounter.

Step 1: Build the prime sieve.

We create a boolean array is_prime of size MX + 1, initialized to True, and set is_prime[0] = is_prime[1] = False since 0 and 1 are not prime. Then we apply the Sieve of Eratosthenes: for every i from 2 up to sqrt(MX), if i is still marked prime, we mark all of its multiples i*i, i*i + i, i*i + 2i, ... as non-prime. Starting from i*i is a small optimization, because smaller multiples have already been marked by smaller prime factors.

After the sieve runs, we extract all prime numbers into a sorted list primes:

primes = [i for i in range(2, MX + 1) if is_prime[i]]

Since we collect them in increasing order, primes is naturally sorted, which lets us use binary search on it later.

Step 2: Traverse the array and accumulate the cost.

We initialize ans = 0 and iterate over nums with both index i and value x:

Even index (i % 2 == 0): We need x to become prime. We use bisect_left(primes, x) to find the position j of the first prime greater than or equal to x. The number of operations required is primes[j] - x, which we add to ans. If x is already prime, primes[j] equals x and the cost is 0.
Odd index: We need x to be non-prime. We check is_prime[x]:
- If x is not prime, no operation is needed.
- If x is prime, we add 2 when x == 2 (since 3 is also prime, we must reach 4), otherwise we add 1 (since x + 1 is even and therefore non-prime for any prime greater than 2).

Finally, we return ans as the minimum number of operations.

Complexity Analysis:

The sieve preprocessing takes O(MX * log log MX) time and O(MX) space, but it runs once and is shared across all test cases.
For each query, the traversal is O(n * log m) time, where n is the length of nums and m is the number of primes in the list (the log m factor comes from the binary search). The extra space per query is O(1).

Example Walkthrough

Let's walk through the solution with a small example: nums = [4, 7, 8].

We need the result to satisfy:

Index 0 (even) → must be prime
Index 1 (odd) → must be non-prime
Index 2 (even) → must be prime

Preprocessing (done once):

Using the Sieve of Eratosthenes, we build is_prime and extract the sorted list of primes:

primes = [2, 3, 5, 7, 11, 13, ...]

This lets us do fast lookups (is_prime[x]) and binary searches (bisect_left).

Step-by-step traversal (initialize ans = 0):

Index 0, value 4 (even → must be prime):

We need the smallest prime ≥ 4.
bisect_left(primes, 4) returns position 2 (since primes[2] = 5 is the first prime ≥ 4).
Cost = primes[2] - 4 = 5 - 4 = 1.
ans = 0 + 1 = 1. (Raise 4 → 5)

Index 1, value 7 (odd → must be non-prime):

Check is_prime[7] → True, so 7 is prime and must be changed.
7 != 2, so the next number 8 is even and non-prime. Cost = 1.
ans = 1 + 1 = 2. (Raise 7 → 8)

Index 2, value 8 (even → must be prime):

We need the smallest prime ≥ 8.
bisect_left(primes, 8) returns position 4 (since primes[4] = 11 is the first prime ≥ 8).
Cost = primes[4] - 8 = 11 - 8 = 3.
ans = 2 + 3 = 5. (Raise 8 → 11)

Final result:

The transformed array is [5, 8, 11], which is alternating prime:

5 (prime) at even index ✓
8 (non-prime) at odd index ✓
11 (prime) at even index ✓

The total minimum number of operations is ans = 5.

Special case note: If an odd index had held the value 2, the cost would be 2 instead of 1, because incrementing 2 → 3 still leaves a prime, so we must go all the way to 4. This walkthrough didn't trigger that case, but it's worth keeping in mind since 2 is the only prime where a single increment is insufficient.

Solution Implementation

1from bisect import bisect_left
2
3# Sieve of Eratosthenes precomputation
4MAX_VAL = 200000
5is_prime = [True] * (MAX_VAL + 1)
6is_prime[0] = is_prime[1] = False  # 0 and 1 are not prime
7
8# Mark all non-prime numbers
9for i in range(2, int(MAX_VAL**0.5) + 1):
10    if is_prime[i]:
11        # Mark multiples of i (starting from i*i) as non-prime
12        for j in range(i * i, MAX_VAL + 1, i):
13            is_prime[j] = False
14
15# Collect all primes up to MAX_VAL for binary search lookups
16primes = [i for i in range(2, MAX_VAL + 1) if is_prime[i]]
17
18
19class Solution:
20    def minOperations(self, nums: list[int]) -> int:
21        total_ops = 0
22
23        for i, x in enumerate(nums):
24            if i % 2 == 0:
25                # Even index: make the value prime.
26                # Find the smallest prime that is >= x.
27                idx = bisect_left(primes, x)
28                # Cost is the difference to reach that prime.
29                total_ops += primes[idx] - x
30            else:
31                # Odd index: make the value non-prime.
32                if is_prime[x]:
33                    # If x is 2, we need 2 operations (push it to 4),
34                    # otherwise 1 operation is enough to reach an adjacent
35                    # non-prime number.
36                    total_ops += 2 if x == 2 else 1
37
38        return total_ops
39

1class Solution {
2    // Upper bound for the prime sieve.
3    private static final int MAX_VALUE = 200_000;
4
5    // isPrime[i] is true if i is a prime number.
6    private static final boolean[] IS_PRIME = new boolean[MAX_VALUE + 1];
7
8    // Sorted list of all primes in the range [2, MAX_VALUE].
9    private static final List<Integer> PRIMES = new ArrayList<>();
10
11    // Static initializer: build the prime sieve once for all test cases.
12    static {
13        // Assume every number is prime initially.
14        Arrays.fill(IS_PRIME, true);
15        // 0 and 1 are not prime.
16        IS_PRIME[0] = false;
17        IS_PRIME[1] = false;
18
19        // Sieve of Eratosthenes.
20        // The condition i <= MAX_VALUE / i is equivalent to i * i <= MAX_VALUE
21        // but avoids potential integer overflow.
22        for (int i = 2; i <= MAX_VALUE / i; ++i) {
23            if (IS_PRIME[i]) {
24                // Mark all multiples of i (starting from i * i) as non-prime.
25                for (int j = i * i; j <= MAX_VALUE; j += i) {
26                    IS_PRIME[j] = false;
27                }
28            }
29        }
30
31        // Collect all primes into a sorted list for binary search.
32        for (int i = 2; i <= MAX_VALUE; ++i) {
33            if (IS_PRIME[i]) {
34                PRIMES.add(i);
35            }
36        }
37    }
38
39    public int minOperations(int[] nums) {
40        // Total number of increment operations needed.
41        int ans = 0;
42
43        for (int i = 0; i < nums.length; ++i) {
44            int x = nums[i];
45
46            if ((i & 1) == 0) {
47                // Even index: the value must become a prime.
48                // Find the smallest prime that is >= x.
49                int j = Collections.binarySearch(PRIMES, x);
50                if (j < 0) {
51                    // Not found exactly; convert to the insertion point,
52                    // which points to the first prime greater than x.
53                    j = -j - 1;
54                }
55                // Cost is the gap between that prime and the current value.
56                ans += PRIMES.get(j) - x;
57            } else if (IS_PRIME[x]) {
58                // Odd index: the value must become non-prime.
59                // If x is 2, +2 makes it 4 (non-prime), since 3 is still prime.
60                // If x is an odd prime, +1 makes it even (non-prime).
61                ans += x == 2 ? 2 : 1;
62            }
63        }
64
65        return ans;
66    }
67}
68

1class Solution {
2public:
3    int minOperations(vector<int>& nums) {
4        int ans = 0;
5        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
6            int x = nums[i];
7            if ((i & 1) == 0) {
8                // Even index: make nums[i] prime by increasing it.
9                // Find the smallest prime >= x, the cost is the difference.
10                auto it = lower_bound(kPrimes.begin(), kPrimes.end(), x);
11                ans += *it - x;
12            } else if (kIsPrime[x]) {
13                // Odd index: make nums[i] non-prime by decreasing it.
14                // If x is 2, the nearest non-prime below is 0 (cost 2);
15                // otherwise just subtract 1 to reach an even non-prime (cost 1).
16                ans += (x == 2) ? 2 : 1;
17            }
18        }
19        return ans;
20    }
21
22private:
23    // Upper bound for the sieve.
24    static constexpr int kMaxValue = 200000;
25
26    // Sieve of Eratosthenes: kIsPrime[v] is true iff v is prime.
27    inline static const vector<bool> kIsPrime = [] {
28        vector<bool> is_prime(kMaxValue + 1, true);
29        is_prime[0] = is_prime[1] = false;
30        for (int i = 2; i <= kMaxValue / i; ++i) {
31            if (is_prime[i]) {
32                // Mark all multiples of i (starting from i*i) as composite.
33                for (int j = i * i; j <= kMaxValue; j += i) {
34                    is_prime[j] = false;
35                }
36            }
37        }
38        return is_prime;
39    }();
40
41    // Sorted list of all primes in the range [2, kMaxValue].
42    inline static const vector<int> kPrimes = [] {
43        vector<int> result;
44        for (int i = 2; i <= kMaxValue; ++i) {
45            if (kIsPrime[i]) {
46                result.push_back(i);
47            }
48        }
49        return result;
50    }();
51};
52

1// Upper bound for the sieve (matches the constraint range of input values).
2const MX = 200000;
3
4/**
5 * Sieve of Eratosthenes.
6 * isPrime[k] is true if and only if k is a prime number.
7 */
8const isPrime: boolean[] = (() => {
9    const prime = new Array<boolean>(MX + 1).fill(true);
10    prime[0] = false;
11    prime[1] = false;
12    // Only need to sieve up to sqrt(MX); the loop bound i <= MX / i enforces that.
13    for (let i = 2; i <= Math.floor(MX / i); ++i) {
14        if (prime[i]) {
15            // Mark every multiple of i starting from i*i as composite.
16            for (let j = i * i; j <= MX; j += i) {
17                prime[j] = false;
18            }
19        }
20    }
21    return prime;
22})();
23
24/**
25 * Sorted list of all prime numbers in the range [2, MX].
26 */
27const primes: number[] = Array.from({ length: MX - 1 }, (_, i) => i + 2).filter(
28    (value) => isPrime[value],
29);
30
31/**
32 * Binary search returning the index of the first element in `arr`
33 * that is greater than or equal to `target` (lower bound).
34 * This mirrors the behavior of lodash's _.sortedIndex.
35 *
36 * @param arr    Ascending-sorted array to search in.
37 * @param target Value to locate the insertion point for.
38 * @returns The leftmost index where `target` could be inserted.
39 */
40function lowerBound(arr: number[], target: number): number {
41    let left = 0;
42    let right = arr.length;
43    while (left < right) {
44        const mid = (left + right) >> 1;
45        if (arr[mid] < target) {
46            left = mid + 1;
47        } else {
48            right = mid;
49        }
50    }
51    return left;
52}
53
54/**
55 * Computes the minimum number of operations so that:
56 *   - elements at even indices become prime, and
57 *   - elements at odd indices become non-prime (composite).
58 * Each unit operation changes a value by 1, but values may not become non-positive,
59 * which is why 2 (the smallest prime) requires 2 operations to turn composite.
60 *
61 * @param nums Input array of positive integers.
62 * @returns Total minimum operations required.
63 */
64function minOperations(nums: number[]): number {
65    let ans = 0;
66    for (let i = 0; i < nums.length; ++i) {
67        const x = nums[i];
68        if ((i & 1) === 0) {
69            // Even index: increase x up to the next prime that is >= x.
70            const j = lowerBound(primes, x);
71            ans += primes[j] - x;
72        } else if (isPrime[x]) {
73            // Odd index: x is prime, so adjust it to the nearest composite.
74            // For x === 2, we must add 2 (to reach 4) because 1 is not composite;
75            // for any larger prime, adding 1 yields an even composite number.
76            ans += x === 2 ? 2 : 1;
77        }
78    }
79    return ans;
80}
81

Time and Space Complexity

Time Complexity: O(n × log P)

The sieve preprocessing runs in O(MX × log log MX) time, but this is a one-time precomputation done outside the Solution class. Focusing on the minOperations method itself, it iterates over the array nums of length n. For each element at an even index, it performs a bisect_left search on the primes list, which costs O(log P) where P is the number of primes in the list. For elements at odd indices, the operation is_prime[x] is a constant-time O(1) lookup. Therefore, the dominant cost per iteration is the binary search, giving a total time complexity of O(n × log P).
Space Complexity: O(P)

The algorithm preprocesses two structures: the is_prime boolean array of size MX + 1, and the primes list which stores all primes up to MX. Both occupy space proportional to the prime-related range, dominated by P (the number of primes and the size of the sieve array). The minOperations method itself uses only a constant number of variables (ans, i, x, j), contributing O(1) auxiliary space. Hence, the overall space complexity is O(P).

Common Pitfalls

Pitfall 1: Incorrectly handling the odd-index case for `x == 2`

The most common mistake at odd indices is assuming that adding 1 to any prime always produces a non-prime number. This logic fails for the smallest prime, 2:

For any prime p > 2, the number p + 1 is even (since all primes greater than 2 are odd), so p + 1 is guaranteed to be non-prime. A single increment suffices.
But 2 + 1 = 3, which is still prime. So one increment is not enough; you must go to 4, requiring 2 operations.

A naive implementation that simply writes total_ops += 1 whenever is_prime[x] is true will undercount the cost whenever a 2 appears at an odd index.

Solution: Special-case x == 2:

if is_prime[x]:
    total_ops += 2 if x == 2 else 1

Pitfall 2: Choosing an insufficient sieve upper bound (`MAX_VAL`)

At even indices we call bisect_left(primes, x) and then read primes[idx]. If x is larger than the largest prime in our precomputed list, bisect_left returns an index equal to len(primes), and primes[idx] throws an IndexError.

This is dangerous because prime gaps mean the next prime above the maximum input value may exceed it. If MAX_VAL only barely covers the maximum allowed input value, an input near that boundary could still need a prime slightly beyond MAX_VAL.

Solution: Pick MAX_VAL comfortably above the constraint's maximum value. Since prime gaps below 2 * 10^5 are small (well under 100), choosing MAX_VAL = 200000 for inputs bounded by, say, 10^5 leaves ample headroom. Always verify that MAX_VAL exceeds the next prime above the largest possible input, not just the input itself.

Pitfall 3: Off-by-one errors in the sieve initialization

Two subtle sieve mistakes frequently appear:

Forgetting to mark 0 and 1 as non-prime. Both default to True after [True] * (MAX_VAL + 1), but neither is prime. Omitting is_prime[0] = is_prime[1] = False corrupts every downstream lookup and binary search.
Wrong range bound when sieving. The outer loop must run up to and including int(MAX_VAL**0.5). Writing range(2, int(MAX_VAL**0.5)) (exclusive) can leave a perfect-square boundary prime's multiples unmarked.

Solution: Initialize explicitly and use + 1 on the loop bound:

is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX_VAL**0.5) + 1):
    ...

Pitfall 4: Misreading `bisect_left` semantics

bisect_left(primes, x) returns the position of the first prime >= x, which is exactly what we want — when x is already prime, it returns the index of x itself, giving a cost of 0. A common mistake is using bisect_right instead, which would skip past x when x is prime and force an unnecessary jump to the next prime, inflating the answer.

Solution: Use bisect_left so that an already-prime value contributes zero cost:

idx = bisect_left(primes, x)   # correct: includes x itself
total_ops += primes[idx] - x

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: