Minimum Cost to Equalize Array

Problem Description

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:

1. Choose an index i from nums and increase nums[i] by 1 for a cost of cost1.
2. 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.

Key Insights

• The goal is to equalize all elements of the array at minimal cost.
• Individual increases (cost1) can be costly compared to paired increases (cost2).
• A binary search or greedy approach can help find the optimal target value for equalization.
• The optimal target can be influenced by the costs associated with individual and paired operations.

Space and Time Complexity

Time Complexity: O(n log(max(nums))) - where n is the number of elements in nums and max(nums) is the maximum value in the array.
Space Complexity: O(1) - only a few additional variables are used for calculations.

Solution

To solve this problem, we can use a binary search approach to find an optimal target value where all elements can be equalized at minimal cost. We will:

1. Define a function to calculate the cost of equalizing the array to a specific target value.
2. Use binary search over the possible target values (from the minimum to the maximum of nums) to find the target that yields the least cost.
3. For each target, compute the total cost by iterating over the array and deciding whether to use individual or paired operations based on the costs provided.

Code Solutions