Skip to main content
Talentd

Minimum Operations to Transform Array into Alternating Prime - Solution & Explanation

MediumArrayMathTwo PointersBinary Search11 min readAsked at: Google
Practice this problem

Problem Statement

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] = 1 to 2, using 1 operation.
  • The element at index 1 must be non-prime. Increment nums[1] = 2 to 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] = 4 to 5, using 1 operation.
  • The element at index 1 is already non-prime.

Total operations = 1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approach Overview

Problem Overview: You are given an array of integers and must transform it into an alternating pattern involving prime numbers. Each operation modifies an element (typically by incrementing or decrementing its value) so that the final array alternates between prime and non‑prime values. The goal is to minimize the total number of operations.

Approach 1: Brute Force Prime Adjustment (O(n * sqrt(V)) time, O(1) space)

Check both possible alternating patterns: prime at even indices and non‑prime at odd indices, or the reverse. For each element, determine whether it already satisfies the required state (prime or non‑prime). If not, compute the minimum number of increments or decrements required to reach the nearest valid number. Primality is checked using trial division up to sqrt(num). This approach is straightforward and useful for smaller value ranges but becomes slow when many prime checks are required.

Approach 2: Precompute Primes with Sieve (O(V log log V + n) time, O(V) space)

Instead of checking primality repeatedly, precompute all primes up to the maximum value range using the Sieve of Eratosthenes. Store them in a boolean array so prime checks become O(1). Then evaluate both alternating patterns by iterating through the array once and computing the minimal distance to a valid prime or non‑prime value when needed. Precomputation removes the repeated sqrt(V) checks and significantly speeds up the evaluation when the array is large.

Approach 3: Greedy Pattern Evaluation (O(n) time after preprocessing, O(V) space)

After building the prime lookup table, iterate through the array while maintaining the expected state (prime or non‑prime) for the current index. If the element already matches the requirement, move forward. Otherwise compute the nearest valid value and add the adjustment cost. Run this process twice—once assuming index 0 should be prime and once assuming it should be non‑prime—and take the minimum result. The greedy insight is that each position can be optimized independently once the pattern is fixed.

Recommended for interviews: The sieve + greedy evaluation approach. Interviewers expect you to reduce repeated prime checks and reason about evaluating two possible patterns. Mention the brute force method first to show baseline reasoning, then optimize with precomputation. This combines concepts from arrays, math, and number theory.

Solution

We can first preprocess a sufficiently large list of prime numbers, denoted as primes, and a boolean array isPrime, where 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 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Prime AdjustmentO(n * sqrt(V))O(1)Small input values where repeated prime checks are cheap
Sieve + Pattern SimulationO(V log log V + n)O(V)General case when array size is large and fast prime lookup is needed
Greedy Alternating EvaluationO(n)O(V)Best choice after sieve preprocessing; optimal for interview solutions

Video Solution

Leetcode 3896 | Minimum Operations to Transform Array into Alternating Prime • CodeWithMeGuys • 184 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Transform Array into Alternating Prime easy or hard?
The problem is typically classified as Medium because it combines multiple concepts: prime detection, greedy evaluation, and handling two possible alternating patterns. The implementation itself is straightforward once you precompute primes efficiently.
Minimum Operations to Transform Array into Alternating Prime Python/Java solution
Implement a sieve to mark primes up to the maximum possible value, then iterate through the array twice for the two possible alternating patterns. Each pass accumulates the cost to convert elements to the required prime or non‑prime state. The same logic works in Python, Java, and C++ with minor syntax differences.
How to solve Minimum Operations to Transform Array into Alternating Prime in O(n)?
After precomputing primes with the Sieve of Eratosthenes, iterate through the array once while enforcing the expected pattern (prime or non‑prime). Compute adjustment cost when the element violates the pattern. Run the process for both possible starting patterns and return the minimum cost, resulting in O(n) traversal after preprocessing.
What is the best approach for Minimum Operations to Transform Array into Alternating Prime?
The most efficient approach uses a Sieve of Eratosthenes to precompute prime numbers and then evaluates two alternating patterns: prime at even indices or prime at odd indices. For each element, calculate the minimal adjustment needed to satisfy the required state. This reduces repeated primality checks and runs in O(V log log V + n) time.
Is Minimum Operations to Transform Array into Alternating Prime asked at Google/Amazon/Meta?
Problems involving prime checks, alternating constraints, and minimal transformations commonly appear in coding interviews at large tech companies. Variations combining arrays with number theory or greedy pattern evaluation are typical in Google and Amazon style interview rounds.
What data structure is used in Minimum Operations to Transform Array into Alternating Prime?
The core data structure is a boolean array or list used for the Sieve of Eratosthenes to store prime information. This allows constant‑time prime checks while iterating through the input array and computing transformation costs.
What is the time complexity of Minimum Operations to Transform Array into Alternating Prime?
The brute force solution runs in O(n * sqrt(V)) because each element may require a trial‑division prime check. Using a sieve to precompute primes reduces repeated checks and improves the complexity to O(V log log V + n), where V is the maximum value considered for prime computation.

Ready to solve this problem?

Practice Minimum Operations to Transform Array into Alternating Prime with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays