Skip to content

Link to Question

HARD

2448. Minimum Cost to Make Array Equal

You are given two arrays nums and cost, both of length n. You can perform the following operation any number of times: - Increase or decrease any element of nums by 1. The cost of changing nums[i] by 1 is cost[i].

Return the minimum cost required to make all elements of nums equal.

Example

Input: 

nums = [1,3,5,2], cost = [2,3,1,14]
Output: 
8
Explanation: Change nums[0] to 2 at a cost of 2, and nums[2] to 2 at a cost of 3. Total cost = 21 + 31 + 13 + 140 = 8.

Constraints

  • n == nums.length == cost.length
  • 1 ≤ n ≤ 10^5
  • 1 ≤ nums[i], cost[i] ≤ 10^6
  • Time Complexity: O(n log X), where X is the range of possible values in nums.
  • Space Complexity: O(1), not counting input and output.
C++
class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int left = *min_element(nums.begin(), nums.end());
        int right = *max_element(nums.begin(), nums.end());
        auto calc = [&](int x) {
            long long res = 0;
            for (int i = 0; i < nums.size(); ++i) {
                res += 1LL * abs(nums[i] - x) * cost[i];
            }
            return res;
        };
        while (left < right) {
            int mid = left + (right - left) / 2;
            long long c1 = calc(mid);
            long long c2 = calc(mid + 1);
            if (c1 <= c2) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return calc(left);
    }
};