Fewest Increment-All-but-One Moves to Make Array Values Equal

You are given an integer array nums. In one move, you choose one element and leave it unchanged while adding 1 to every other element. Return the minimum number of moves needed to make all elements equal.

Function Signature

def min_moves_to_equal(nums: list[int]) -> int:

Rules

• Each move adds exactly 1 to every element except the one chosen.
• The chosen element can be different from one move to the next.
• An array whose elements are already all equal, including a single-element array, needs 0 moves.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• The answer can reach about 2 * 10^14, which exceeds the 32-bit signed range but stays below 2^53.

Examples

Example 1

Input:  nums = [1, 3]
Output: 2

Keep 3 unchanged twice: [1, 3] becomes [2, 3] and then [3, 3].

Example 2

Input:  nums = [4, 1, 6]
Output: 8

Example 3

Input:  nums = [-2, 5, -2, 0]
Output: 9

Equalize an Array by Raising All but One Element

Hints

1. Look at what a single move does to the gap between any two elements, not to their absolute values.
2. Simulating the moves one at a time is far too slow when the answer can reach about 2 * 10^14.
3. The answer can exceed the 32-bit signed range, so accumulate it in a 64-bit integer.

Approach

Whether all elements are equal depends only on the differences between pairs of elements. A move that adds 1 to every element except element i changes every pairwise difference exactly as subtracting 1 from element i alone would. So the problem is equivalent to one where a move subtracts 1 from a single chosen element, and the move counts are identical.

In that equivalent view, no element ever increases, so the common final value t cannot exceed min(nums). Each element x needs exactly x - t decrements to reach t, giving sum(x - t) moves, which is smallest when t = min(nums). That bound is achievable: decrement every element down to the minimum (in the original problem, choose element i once for each unit by which it exceeds the minimum). The answer is therefore sum(nums[i] - min(nums)).

The algorithm makes one pass to find the minimum and a second pass to add each element's excess over it. Edge cases: a single element or an all-equal array gives 0. Negative values need no special handling because only differences matter. Each difference is at most 2 * 10^9, and the total can reach (10^5 - 1) * 2 * 10^9, about 2 * 10^14. The sum therefore needs a 64-bit accumulator: Java casts each element to long before subtracting, and C++ uses long long. The total stays below 2^53, so JavaScript numbers hold it exactly.

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