Minimum cost to equalize array

Array Greedy Enumeration

18.7% acceptance

Feb 24, 2026

149

You are given an integer array nums and two integers cost1 and cost2. You are allowed to perform either of the following operations any number of times: Choose an index i from nums and increase nums[i] by 1 for a cost of cost1. Choose two different indices i, j, from nums and increase nums[i] and nums[j] by 1 for a cost of cost2. Return the minimum cost required to make all elements in the array equal. Since the answer may be very large, return it modulo 10^9 + 7.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost_to_equalize_array(nums: Vec<i32>, cost1: i32, cost2: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let c1 = cost1 as i64;
    let c2 = cost2 as i64;
    let n = nums.len() as i64;
    let max_val = *nums.iter().max().unwrap() as i64;
    let min_val = *nums.iter().min().unwrap() as i64;
    let sum_nums: i64 = nums.iter().map(|&x| x as i64).sum();

    let total0 = n * max_val - sum_nums;
    if total0 == 0 {
      return 0;
    }

    // If singles always cheaper, or n <= 2 (can't form useful pairs from imbalance)
    if 2 * c1 <= c2 || n <= 2 {
      return ((total0 % MOD) * c1 % MOD) as i32;
    }

    // n >= 3, cost2 < 2*cost1: prefer pairs when possible
    let max_diff0 = max_val - min_val;

    // Returns the raw (unmodded) cost for comparison purposes.
    // pairs * c2 + singles * c1; values fit in i64 for the given constraints.
    let best_cost_raw = |total: i64, max_diff: i64| -> i64 {
      let (pairs, singles) = if max_diff * 2 <= total {
        (total / 2, total % 2)
      } else {
        (total - max_diff, 2 * max_diff - total)
      };
      pairs * c2 + singles * c1
    };

    let mut best_raw = best_cost_raw(total0, max_diff0);

    // Determine the range of k to try
    let k_start = if 2 * max_diff0 > total0 {
      // Minimum k to reach balanced state
      let excess = 2 * max_diff0 - total0;
      (excess + n - 3) / (n - 2) // ceil(excess / (n-2))
    } else {
      0
    };

    // Always try k_start-1 through k_start+2 to catch parity improvements
    // k must be >= 0 (target can only increase, not decrease below max_val)
    let k_lo = if k_start > 0 { k_start - 1 } else { 0 };
    for k in k_lo..=k_start + 2 {
      let total_k = total0 + n * k;
      let max_diff_k = max_diff0 + k;
      let raw = best_cost_raw(total_k, max_diff_k);
      best_raw = best_raw.min(raw);
    }

    // Apply mod only to the winning raw cost
    (best_raw % MOD) as i32
  }
}