453. Minimum Moves to Equal Array Elements
- Array
- Math
TIME
O(n)
SPACE
O(1)
Intuition
Adding 1 to every element except one changes the differences between elements exactly as subtracting 1 from that one element would. Only the differences matter for "all equal", so each move is really "decrease one element by 1". The cheapest target is then the minimum, since nothing can go below it without wasting moves, and every element x needs x - min moves to get there.
Approach
- Find
min(nums). - Return
sum(x - min for x in nums), which equalssum(nums) - n * min(nums).
Complexity
- Time: O(n)
- Space: O(1)
Edge Cases
- One element or all equal: 0 moves
- Negative values: only the differences matter, so the formula is unchanged
sum(nums)alone can reach 10^14 andn * mincan be just as large, so Java sums the differencesx - minin along; the final answer fits in anintby the problem's guarantee
Code
class Solution:
def minMoves(self, nums: list[int]) -> int:
"""
453. Minimum Moves to Equal Array Elements
Time: O(n)
Space: O(1)
"""
# Raising n - 1 elements by 1 is the same, relative to each other, as
# lowering the remaining one by 1. So bring every element down to the min.
return sum(nums) - len(nums) * min(nums)/**
* 453. Minimum Moves to Equal Array Elements
* Time: O(n)
* Space: O(1)
*/
class Solution {
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE;
for (int x : nums) {
min = Math.min(min, x);
}
// Raising n - 1 elements by 1 is the same, relative to each other, as
// lowering the remaining one by 1. So bring every element down to the min.
long moves = 0;
for (int x : nums) {
moves += (long) x - min;
}
return (int) moves;
}
}