Minimum Moves to Equal Array Elements

How it works

Increasing n - 1 values is equivalent, up to a shared shift, to decreasing the one excluded value. Reduce every value to the minimum and sum the required decreases. This counts the original operations without simulating them.

Steps

1. Find the minimum array value.
2. Sum each value minus the minimum.
3. Return the total.

Complexity

• Time: O(n).
• Space: O(1).

Things to watch for

• Use the minimum, rather than the maximum or median.
• Negative values work with the same differences.
• The original operation increases all but one value.

class Solution:
  def minMoves(self, nums: list[int]) -> int:
    mn = min(nums)
    return sum(num - mn for num in nums)

class Solution {
 public:
  int minMoves(vector<int>& nums) {
    const int mn = ranges::min(nums);
    return accumulate(nums.begin(), nums.end(), 0,
                      [&](int acc, int num) { return acc + (num - mn); });
  }
};