Skip to main content
Back to problems
#3896
Medium Algorithms

Minimum operations to transform array into alternating prime

53.1% acceptance
May 13, 2026
60
4
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.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    let max_v = *nums.iter().max().unwrap_or(&1) as usize;
    let lim = (max_v + 16).max(8) * 2;
    let mut is_prime = vec![true; lim];
    is_prime[0] = false;
    is_prime[1] = false;
    let mut i = 2usize;
    while i * i < lim {
      if is_prime[i] {
        let mut j = i * i;
        while j < lim {
          is_prime[j] = false;
          j += i;
        }
      }
      i += 1;
    }
    let mut next_prime = vec![0i32; lim];
    let mut next_nonprime = vec![0i32; lim];
    let mut lp: i32 = -1;
    let mut ln: i32 = -1;
    for v in (0..lim).rev() {
      if is_prime[v] { lp = v as i32; }
      else { ln = v as i32; }
      next_prime[v] = lp;
      next_nonprime[v] = ln;
    }
    let mut total = 0i64;
    for (idx, &v) in nums.iter().enumerate() {
      let v = v as usize;
      let target = if idx % 2 == 0 { next_prime[v] } else { next_nonprime[v] };
      total += (target as i64 - v as i64).max(0);
    }
    total as i32
  }
}