We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Equalize Array

Number: 3402

Difficulty: Hard

Paid? No

Companies: Microsoft, Amazon

Problem Description

Given an integer array nums and two operation costs (cost1 and cost2), we want to make all elements in the array equal by only increasing elements. There are two allowed operations which may be applied any number of times: • Increase a single element by 1 at a cost of cost1. • Increase two different elements by 1 in a single operation at a cost of cost2. Return the minimum total cost required to make all array elements equal. Since the answer can be large, report it modulo 10^9 + 7.

Key Insights

  • Since only increases are allowed, the target value must be at least the maximum element in nums.
  • For each element, the number of increments needed is (target - current_value).
  • If cost2 is not cheaper than doing two separate single increments (i.e. if cost2 ≥ 2×cost1), then it is optimal to just perform single increments.
  • If cost2 < 2×cost1, then it is beneficial to pair up increments across two different indices. However, a pairing is possible only if there is “overlap” — the maximum number of pair operations is limited by the total increments needed minus the increments needed by the element that requires the most (since an operation needs two distinct indices).
  • The maximum number of pair operations equals min(floor(total_increments/2), total_increments - max_increments_on_a_single_element).
  • Finally, the total cost is the cost for all increments (all increments done individually) reduced by the saving per pair operation (which is 2×cost1 - cost2) multiplied by the number of pairs used.

Space and Time Complexity

Time Complexity: O(n) – we perform a single pass (or constant number of passes) through the array. Space Complexity: O(1) – only a few extra variables are used aside from the input.

Solution

We first choose the target value as the maximum element in nums since only increases are allowed. For each element in the array, compute the difference (target - element) and sum these differences, denoted as total_increments. Also, determine the maximum difference (which will occur for the minimum element in the array). If cost2 is not beneficial (i.e. cost2 ≥ 2×cost1), simply pay cost1 per increment.

If cost2 is beneficial (cost2 < 2×cost1), calculate the maximum pairs you can perform, which is the minimum of (total_increments // 2) and (total_increments - max_diff). Each pair operation saves (2×cost1 - cost2) compared to doing two single increments separately. Thus, the minimum total cost becomes (total_increments × cost1) minus (pairs × (2×cost1 - cost2)). Return the result modulo (10^9 + 7).

Code Solutions

# Define the function to compute the minimum cost.
def minCostEqualizeArray(nums, cost1, cost2):
    mod = 10**9 + 7
    # The target is the maximum value in the array because only increases are allowed.
    target = max(nums)
    total_increments = 0  # Sum of increments needed for all elements.
    max_needed = 0        # Maximum increments needed for any single element.
    
    # Calculate differences for each element.
    for num in nums:
        diff = target - num
        total_increments += diff
        if diff > max_needed:
            max_needed = diff

    # If pairing is not beneficial, use only single increment operations.
    if cost2 >= 2 * cost1:
        return (total_increments * cost1) % mod

    # Calculate the maximum possible pair operations.
    # Each pair operation uses increments from two distinct indices.
    max_pairs = min(total_increments // 2, total_increments - max_needed)
    
    # Each pair saves (2 * cost1 - cost2) compared to performing two single operations.
    total_cost = (total_increments * cost1 - max_pairs * (2 * cost1 - cost2)) % mod
    return total_cost

# Example usage:
print(minCostEqualizeArray([4,1], 5, 2))        # Expected output: 15
print(minCostEqualizeArray([2,3,3,3,5], 2, 1))    # Expected output: 6
print(minCostEqualizeArray([3,5,3], 1, 3))        # Expected output: 4
← Back to All Questions