Prime subtraction operation

Array Math Binary Search Greedy Number Theory

55.6% acceptance

Feb 25, 2026

941

You are given a 0-indexed integer array nums of length n. You can perform the following operation as many times as you want: Pick an index i that you haven't picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i]. Return true if you can make nums a strictly increasing array using the above operation and false otherwise. A strictly increasing array is an array whose each element is strictly greater than its preceding element.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn prime_sub_operation(nums: Vec<i32>) -> bool {
    // Sieve of Eratosthenes up to 1000
    let limit = 1001usize;
    let mut is_prime = vec![true; limit];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..limit {
      if is_prime[i] {
        let mut j = i * i;
        while j < limit {
          is_prime[j] = false;
          j += i;
        }
      }
    }
    let primes: Vec<i32> = (2..limit).filter(|&i| is_prime[i]).map(|i| i as i32).collect();

    let mut prev = 0i32;
    for &n in &nums {
      // We want n - p > prev, i.e., p < n - prev
      // Find the largest prime < (n - prev)
      let bound = n - prev; // p must be < bound and < n
      if bound <= 1 {
        // No prime to subtract, n must be > prev
        if n <= prev {
          return false;
        }
        prev = n;
      } else {
        // Find largest prime < bound
        let p = primes.iter().rev().find(|&&p| p < bound).copied();
        let new_val = if let Some(p) = p { n - p } else { n };
        if new_val <= prev {
          return false;
        }
        prev = new_val;
      }
    }
    true
  }
}