Fewest Increment-All-but-One Moves to Make Array Values Equal
Company: Squarepoint
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
Input: nums = [1, 3]
Output: 2
```
Keep `3` unchanged twice: `[1, 3]` becomes `[2, 3]` and then `[3, 3]`.
**Example 2**
```text
Input: nums = [4, 1, 6]
Output: 8
```
**Example 3**
```text
Input: nums = [-2, 5, -2, 0]
Output: 9
```
Overview: From a Squarepoint technical screen: one move adds 1 to every element of an integer array except one chosen element, and you must find the fewest moves that make all elements equal. It tests reasoning about what each move really changes, along with negative values and answers beyond the 32-bit range.
Read the full Squarepoint Data Scientist interview experience this question came from
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.
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.
Return the answer as an integer. The answer can reach about 2 * 10^14, which exceeds the 32-bit signed range (2^31 - 1) but stays below 2^53, so return it as a 64-bit integer (`long` in Java, `long long` in C++). Every individual element fits in a 32-bit signed integer.
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.
Example 1:
Input: nums = [1, 3]
Output: 2
Explanation: Keep 3 unchanged twice: [1, 3] becomes [2, 3] and then [3, 3].
Example 2:
Input: nums = [4, 1, 6]
Output: 8
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
Input: ([7],)
Expected Output: 0
Explanation: Minimum valid: a single-element array is already equal and needs 0 moves.
Input: ([1, 3],)
Expected Output: 2
Explanation: Source Example 1: keep 3 unchanged twice.
Hints
- Look at what a single move does to the gap between any two elements, not to their absolute values.
- Simulating the moves one at a time is far too slow when the answer can reach about 2 * 10^14.
- The answer can exceed the 32-bit signed range, so accumulate it in a 64-bit integer.