Minimum division operations to make array non decreasing

Array Math Greedy Number Theory

29.1% acceptance

Feb 23, 2026

134

You are given an integer array nums. Any positive divisor of a natural number x that is strictly less than x is called a proper divisor of x. For example, 2 is a proper divisor of 4, while 6 is not a proper divisor of 6. You are allowed to perform an operation any number of times on nums, where in each operation you select any one element from nums and divide it by its greatest proper divisor. Return the minimum number of operations required to make the array non-decreasing. If it is not possible to make the array non-decreasing using any number of operations, return -1.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    // Greatest proper divisor of x = x / smallest_prime_factor(x)
    // After dividing by gpd: result = smallest_prime_factor(x)
    // So each element can be reduced to its smallest prime factor (in 1 operation)
    // or kept as is. We process right to left.
    // For each element, if nums[i] > nums[i+1], we must reduce nums[i].
    // After reducing: nums[i] = spf(nums[i]). If spf(nums[i]) > nums[i+1], return -1.
    
    // Precompute smallest prime factors using sieve
    let max_val = *nums.iter().max().unwrap() as usize;
    let mut spf = vec![0usize; max_val + 1];
    for i in 2..=max_val { spf[i] = i; }
    let mut i = 2;
    while i * i <= max_val {
      if spf[i] == i {
        let mut j = i * i;
        while j <= max_val {
          if spf[j] == j { spf[j] = i; }
          j += i;
        }
      }
      i += 1;
    }
    
    let n = nums.len();
    let mut ops = 0;
    let mut prev = nums[n - 1] as usize;
    
    for i in (0..n - 1).rev() {
      let cur = nums[i] as usize;
      if cur <= prev {
        prev = cur;
      } else {
        // Must reduce cur to spf[cur]
        let reduced = spf[cur];
        if reduced > prev {
          return -1;
        }
        ops += 1;
        prev = reduced;
      }
    }
    ops
  }
}