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 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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^5
  • 1 <= nums[i] <= 10^6
  • 1 <= cost1 <= 10^6
  • 1 <= 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

  1. Find the maximum value in nums (let’s call it mx).
  2. For each possible target value from mx to mx + 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.
  3. Return the minimum cost modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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).