Minimum Cost to Equalize Array
HardUpdated: Aug 2, 2025
Practice on:
Problem
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
ifromnumsand increasenums[i]by1for a cost ofcost1. - Choose two different indices
i,j, fromnumsand increasenums[i]andnums[j]by1for a cost ofcost2.
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.
Examples
Example 1
Input: nums = [4,1], cost1 = 5, cost2 = 2
Output: 15
Explanation:
The following operations can be performed to make the values equal:
* Increase `nums[1]` by 1 for a cost of 5. `nums` becomes `[4,2]`.
* Increase `nums[1]` by 1 for a cost of 5. `nums` becomes `[4,3]`.
* Increase `nums[1]` by 1 for a cost of 5. `nums` becomes `[4,4]`.
The total cost is 15.
Example 2
Input: nums = [2,3,3,3,5], cost1 = 2, cost2 = 1
Output: 6
Explanation:
The following operations can be performed to make the values equal:
* Increase `nums[0]` and `nums[1]` by 1 for a cost of 1. `nums` becomes `[3,4,3,3,5]`.
* Increase `nums[0]` and `nums[2]` by 1 for a cost of 1. `nums` becomes `[4,4,4,3,5]`.
* Increase `nums[0]` and `nums[3]` by 1 for a cost of 1. `nums` becomes `[5,4,4,4,5]`.
* Increase `nums[1]` and `nums[2]` by 1 for a cost of 1. `nums` becomes `[5,5,5,4,5]`.
* Increase `nums[3]` by 1 for a cost of 2. `nums` becomes `[5,5,5,5,5]`.
The total cost is 6.
Example 3
Input: nums = [3,5,3], cost1 = 1, cost2 = 3
Output: 4
Explanation:
The following operations can be performed to make the values equal:
* Increase `nums[0]` by 1 for a cost of 1. `nums` becomes `[4,5,3]`.
* Increase `nums[0]` by 1 for a cost of 1. `nums` becomes `[5,5,3]`.
* Increase `nums[2]` by 1 for a cost of 1. `nums` becomes `[5,5,4]`.
* Increase `nums[2]` by 1 for a cost of 1. `nums` becomes `[5,5,5]`.
The total cost is 4.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^61 <= cost1 <= 10^61 <= cost2 <= 10^6
Solution
Method 1 – Greedy Enumeration
Intuition
To make all elements equal, we can choose a target value and calculate the cost to increase all elements to that value. For each element, we can use either single or double increment operations. Using as many double operations as possible is optimal if cost2 < 2 * cost1.
Approach
- Find the maximum value in
nums(let's call itmx). - For each possible target value from
mxtomx + max(nums):- For each element, calculate the difference to the target.
- Use as many double operations as possible (pairs of increments), and single operations for the remainder.
- Compute the total cost for this target.
- Track the minimum cost.
- Return the minimum cost modulo
10^9 + 7.
Code
C++
class Solution {
public:
int minCostToEqualizeArray(vector<int>& nums, int cost1, int cost2) {
int mx = *max_element(nums.begin(), nums.end());
int ans = INT_MAX;
for (int tgt = mx; tgt <= mx + *max_element(nums.begin(), nums.end()); ++tgt) {
int cnt1 = 0, cnt2 = 0;
for (int x : nums) {
int d = tgt - x;
cnt2 += d / 2;
cnt1 += d % 2;
}
int cur = cnt1 * cost1 + cnt2 * min(cost2, 2 * cost1);
ans = min(ans, cur);
}
return ans % 1000000007;
}
};
Go
func minCostToEqualizeArray(nums []int, cost1, cost2 int) int {
mx := nums[0]
for _, v := range nums {
if v > mx { mx = v }
}
ans := 1<<62
for tgt := mx; tgt <= mx+mx; tgt++ {
cnt1, cnt2 := 0, 0
for _, x := range nums {
d := tgt - x
cnt2 += d / 2
cnt1 += d % 2
}
cur := cnt1*cost1 + cnt2*min(cost2, 2*cost1)
if cur < ans { ans = cur }
}
return ans % 1000000007
}
Java
class Solution {
public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) {
int mx = Arrays.stream(nums).max().getAsInt();
int ans = Integer.MAX_VALUE;
for (int tgt = mx; tgt <= mx + mx; ++tgt) {
int cnt1 = 0, cnt2 = 0;
for (int x : nums) {
int d = tgt - x;
cnt2 += d / 2;
cnt1 += d % 2;
}
int cur = cnt1 * cost1 + cnt2 * Math.min(cost2, 2 * cost1);
ans = Math.min(ans, cur);
}
return ans % 1000000007;
}
}
Kotlin
class Solution {
fun minCostToEqualizeArray(nums: IntArray, cost1: Int, cost2: Int): Int {
val mx = nums.maxOrNull()!!
var ans = Int.MAX_VALUE
for (tgt in mx..(mx + mx)) {
var cnt1 = 0; var cnt2 = 0
for (x in nums) {
val d = tgt - x
cnt2 += d / 2
cnt1 += d % 2
}
val cur = cnt1 * cost1 + cnt2 * minOf(cost2, 2 * cost1)
ans = minOf(ans, cur)
}
return ans % 1000000007
}
}
Python
class Solution:
def minCostToEqualizeArray(self, nums: list[int], cost1: int, cost2: int) -> int:
mx = max(nums)
ans = float('inf')
for tgt in range(mx, mx + max(nums) + 1):
cnt1, cnt2 = 0, 0
for x in nums:
d = tgt - x
cnt2 += d // 2
cnt1 += d % 2
cur = cnt1 * cost1 + cnt2 * min(cost2, 2 * cost1)
ans = min(ans, cur)
return ans % 1000000007
Rust
impl Solution {
pub fn min_cost_to_equalize_array(nums: Vec<i32>, cost1: i32, cost2: i32) -> i32 {
let mx = *nums.iter().max().unwrap();
let mut ans = i32::MAX;
for tgt in mx..=mx+mx {
let mut cnt1 = 0;
let mut cnt2 = 0;
for &x in &nums {
let d = tgt - x;
cnt2 += d / 2;
cnt1 += d % 2;
}
let cur = cnt1 * cost1 + cnt2 * cost2.min(2 * cost1);
ans = ans.min(cur);
}
ans % 1000000007
}
}
TypeScript
class Solution {
minCostToEqualizeArray(nums: number[], cost1: number, cost2: number): number {
const mx = Math.max(...nums);
let ans = Number.MAX_SAFE_INTEGER;
for (let tgt = mx; tgt <= mx + mx; ++tgt) {
let cnt1 = 0, cnt2 = 0;
for (const x of nums) {
const d = tgt - x;
cnt2 += Math.floor(d / 2);
cnt1 += d % 2;
}
const cur = cnt1 * cost1 + cnt2 * Math.min(cost2, 2 * cost1);
ans = Math.min(ans, cur);
}
return ans % 1000000007;
}
}
Complexity
- ⏰ Time complexity:
O(n * R)where n is the length of nums and R is the range of possible target values. - 🧺 Space complexity:
O(1).