Minimum operations to make the array beautiful

Array Dynamic Programming

38.0% acceptance

Mar 31, 2026

You are given an integer array nums. An array is called beautiful if for every index i > 0, the value at nums[i] is divisible by nums[i - 1]. In one operation, you may increment any element nums[i] (with i > 0) by 1. Return the minimum number of operations required to make the array beautiful.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    // Greedy (always pick smallest multiple) is not optimal — a slightly larger
    // multiple at position i can reduce the cost at i+1 significantly.
    // Use DP: dp[v] = min total ops so far with current element equal to v.
    // Bound: each v_i <= nums[i] + total_greedy_cost <= 50 + 4950 = 5000.
    const MAX_VAL: usize = 5001;
    let inf = i32::MAX / 2;
    let mut dp = vec![inf; MAX_VAL];
    dp[nums[0] as usize] = 0;

    for i in 1..nums.len() {
      let curr = nums[i] as usize;
      let mut new_dp = vec![inf; MAX_VAL];

      for p in 1..MAX_VAL {
        if dp[p] >= inf {
          continue;
        }
        let start_k = (curr + p - 1) / p;
        let mut k = start_k;
        loop {
          let v = k * p;
          if v >= MAX_VAL {
            break;
          }
          let cost = dp[p] + (v - curr) as i32;
          if new_dp[v] > cost {
            new_dp[v] = cost;
          }
          k += 1;
        }
      }

      dp = new_dp;
    }

    *dp.iter().filter(|&&v| v < inf).min().unwrap()
  }
}