# LeetCode 453: Minimum Moves to Equal Array Elements

## Problem Restatement

We are given an integer array `nums`.

In one move, we can increment exactly `n - 1` elements by `1`, where `n` is the length of the array.

That means each move leaves one element unchanged and increases every other element.

We need to return the minimum number of moves required to make all elements equal. The official statement defines this move as incrementing `n - 1` elements by `1`.

For example:

```python
nums = [1, 2, 3]
```

One possible sequence is:

```python
[1, 2, 3]
[2, 3, 3]
[3, 4, 3]
[4, 4, 4]
```

So the answer is:

```python
3
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Minimum number of moves |
| Move | Increment exactly `n - 1` elements by `1` |
| Goal | Make every element equal |

Function shape:

```python
def minMoves(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3]
```

The answer is:

```python
3
```

Explanation:

```python
[1, 2, 3] -> [2, 3, 3]
[2, 3, 3] -> [3, 4, 3]
[3, 4, 3] -> [4, 4, 4]
```

Example 2:

```python
nums = [1, 1, 1]
```

All elements are already equal.

The answer is:

```python
0
```

Example 3:

```python
nums = [5, 6, 8]
```

The minimum element is `5`.

The differences from the minimum are:

```python
5 - 5 = 0
6 - 5 = 1
8 - 5 = 3
```

The answer is:

```python
0 + 1 + 3 = 4
```

## First Thought: Simulate the Moves

A direct idea is to repeatedly increment all elements except the current largest element.

For example:

```python
nums = [1, 2, 3]
```

The largest element is `3`, so increment the other two:

```python
[1, 2, 3] -> [2, 3, 3]
```

Then the largest element is still one of the `3`s, so increment the other two:

```python
[2, 3, 3] -> [3, 4, 3]
```

Then:

```python
[3, 4, 3] -> [4, 4, 4]
```

This gives the right answer for small arrays, but simulation is a poor solution.

## Problem With Simulation

The number of moves can be large.

For example:

```python
nums = [1, 1000000000]
```

Each move increments only one of the two elements.

The answer is:

```python
999999999
```

Simulating nearly one billion moves is too slow.

We need a formula.

## Key Insight

Incrementing `n - 1` elements by `1` has the same relative effect as decrementing the one untouched element by `1`.

For equality, only the differences between numbers matter.

Consider:

```python
[1, 2, 3]
```

If we increment the first two elements:

```python
[1, 2, 3] -> [2, 3, 3]
```

Relative to subtracting `1` from every element, this is equivalent to:

```python
[1, 2, 3] -> [1, 2, 2]
```

The largest element effectively moved down by `1`.

So instead of thinking:

“Increment `n - 1` elements.”

Think:

“Decrement one element.”

To make all elements equal with the fewest moves, we reduce every element down to the minimum element.

So the answer is the sum of differences from the minimum.

## Formula

Let:

```python
mn = min(nums)
```

Every number `num` needs:

```python
num - mn
```

effective decrements to reach `mn`.

So the total number of moves is:

```python
sum(num - mn for num in nums)
```

This is the same as:

```python
sum(nums) - len(nums) * min(nums)
```

## Algorithm

Find the minimum value in the array:

```python
mn = min(nums)
```

Initialize `moves = 0`.

For each number `num` in `nums`, add its difference from the minimum:

```python
moves += num - mn
```

Return `moves`.

## Correctness

Each move increments `n - 1` elements and leaves one element unchanged.

Compared to all elements moving together, this is equivalent to decreasing the unchanged element by `1`.

Therefore, the problem becomes equivalent to reducing selected elements by `1` until all elements become equal.

The smallest element is the lowest value all elements can be reduced to without needing to reduce it below its original value.

For any element `num`, it must be effectively reduced by exactly:

```python
num - min(nums)
```

to reach the minimum value.

Summing this over all elements gives the total number of required effective decrements.

Each effective decrement corresponds to one original move.

Therefore, the algorithm returns the minimum number of moves.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the array to find the minimum and compute the sum |
| Space | `O(1)` | We only store a few variables |

## Implementation

```python
class Solution:
    def minMoves(self, nums: list[int]) -> int:
        mn = min(nums)
        moves = 0

        for num in nums:
            moves += num - mn

        return moves
```

A shorter version:

```python
class Solution:
    def minMoves(self, nums: list[int]) -> int:
        return sum(nums) - len(nums) * min(nums)
```

## Code Explanation

We first find the smallest element:

```python
mn = min(nums)
```

Then we count how far every element is above that minimum:

```python
for num in nums:
    moves += num - mn
```

If a number already equals `mn`, it contributes `0`.

If a number is larger than `mn`, it contributes the number of effective decrements needed to bring it down to `mn`.

Finally:

```python
return moves
```

returns the minimum number of moves.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minMoves([1, 2, 3]) == 3
    assert s.minMoves([1, 1, 1]) == 0
    assert s.minMoves([5, 6, 8]) == 4
    assert s.minMoves([1, 1000000000]) == 999999999
    assert s.minMoves([-1, 0, 1]) == 3
    assert s.minMoves([10]) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3]` | Standard example |
| `[1, 1, 1]` | Already equal |
| `[5, 6, 8]` | General case |
| `[1, 1000000000]` | Large answer without simulation |
| `[-1, 0, 1]` | Negative numbers |
| `[10]` | Single element |