3139. Minimum Cost to Equalize Array LeetCode Solution
In this guide, you will get 3139. Minimum Cost to Equalize Array LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Equalize Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Cost to Equalize Array
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 109 + 7.
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].
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].
3139. Minimum Cost to Equalize Array LeetCode Solution in C++
class Solution {
public:
int minCostToEqualizeArray(vector<int>& nums, int cost1, int cost2) {
constexpr int kMod = 1'000'000'007;
const int n = nums.size();
const int minNum = ranges::min(nums);
const int maxNum = ranges::max(nums);
const long sum = accumulate(nums.begin(), nums.end(), 0L);
long ans = LONG_MAX;
if (cost1 * 2 <= cost2 || n < 3) {
const long totalGap = static_cast<long>(maxNum) * n - sum;
return (cost1 * totalGap) % kMod;
}
for (int target = maxNum; target < 2 * maxNum; ++target) {
const int maxGap = target - minNum;
const long totalGap = static_cast<long>(target) * n - sum;
const long pairs = min(totalGap / 2, totalGap - maxGap);
ans = min(ans, cost1 * (totalGap - 2 * pairs) + cost2 * pairs);
}
return ans % kMod;
}
}; /* code provided by PROGIEZ */
3139. Minimum Cost to Equalize Array LeetCode Solution in Java
class Solution {
public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) {
final int kMod = 1_000_000_007;
final int n = nums.length;
final int minNum = Arrays.stream(nums).min().getAsInt();
final int maxNum = Arrays.stream(nums).max().getAsInt();
final long sum = Arrays.stream(nums).asLongStream().sum();
long ans = Long.MAX_VALUE;
if (cost1 * 2 <= cost2 || n < 3) {
final long totalGap = 1L * maxNum * n - sum;
return (int) ((cost1 * totalGap) % kMod);
}
for (int target = maxNum; target < 2 * maxNum; ++target) {
final int maxGap = target - minNum;
final long totalGap = 1L * target * n - sum;
final long pairs = Math.min(totalGap / 2, totalGap - maxGap);
ans = Math.min(ans, cost1 * (totalGap - 2 * pairs) + cost2 * pairs);
}
return (int) (ans % kMod);
}
} // code provided by PROGIEZ
3139. Minimum Cost to Equalize Array LeetCode Solution in Python
class Solution:
def minCostToEqualizeArray(
self,
nums: list[int],
cost1: int,
cost2: int,
) -> int:
kMod = 1_000_000_007
n = len(nums)
minNum = min(nums)
maxNum = max(nums)
summ = sum(nums)
if cost1 * 2 <= cost2 or n < 3:
totalGap = maxNum * n - summ
return (cost1 * totalGap) % kMod
def getMinCost(target: int) -> int:
"""Returns the minimum cost to make all numbers equal to `target`."""
maxGap = target - minNum
totalGap = target * n - summ
# Pair one shallowest number with one non-shallowest number, so the worst
# case is that we have `totalGap - maxGap` non-shallowest numbers to pair.
pairs = min(totalGap // 2, totalGap - maxGap)
return cost1 * (totalGap - 2 * pairs) + cost2 * pairs
return min(getMinCost(target)
for target in range(maxNum, 2 * maxNum)) % kMod # code by PROGIEZ
