967. Weighted Equaliser
A workshop has n machines whose settings are the integers nums[i]. Changing the setting of machine i by one step, up or down, costs cost[i] units, so moving it by d steps costs d * cost[i]. Settings may be changed any number of times and may end at any integer.
Return the minimum total cost required to make all machines show the same setting. Note that the shared setting does not need to be one of the starting values, but you can always find an optimal one among them. Return the cost as a 64-bit integer.
Example 1
- Input:
- nums = [2,6,10], cost = [1,1,1]
- Output:
- 8
- Explanation:
With equal costs the median 6 is best: (4 + 0 + 4) = 8.
Example 2
- Input:
- nums = [1,4], cost = [5,1]
- Output:
- 3
- Explanation:
Moving the cheap number 4 down to 1 costs 3 * 1 = 3, while moving 1 up to 4 would cost 3 * 5 = 15.
Example 3
- Input:
- nums = [7], cost = [3]
- Output:
- 0
- Explanation:
A single number is already equal to itself.
Constraints
- 1 ≤ nums.length ≤ 105
- nums.length == cost.length
- 1 ≤ nums[i] ≤ 106
- 1 ≤ cost[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)