Minimum replacements to sort the array

Array Math Greedy

53.2% acceptance

Feb 25, 2026

2080

You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it. For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7]. Return the minimum number of operations to make an array that is sorted in non-decreasing order.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_replacement(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    if n == 0 { return 0; }
    let mut ans = 0i64;
    let mut prev = nums[n - 1] as i64;
    for i in (0..n - 1).rev() {
      let x = nums[i] as i64;
      if x <= prev {
        prev = x;
      } else {
        let k = (x + prev - 1) / prev; // ceil(x/prev)
        ans += k - 1;
        prev = x / k; // smallest piece
      }
    }
    ans
  }
}