# LeetCode 292: Nim Game

## Problem Restatement

We are given a heap with `n` stones.

Two players take turns removing stones from the heap.

On each turn, a player must remove:

```python
1, 2, or 3
```

stones.

You go first.

The player who removes the last stone wins.

We need to return `True` if we can force a win assuming both players play optimally. Otherwise, return `False`.

The source statement gives the same rules: there is one heap, you go first, each player removes `1` to `3` stones, and the player who removes the last stone wins. The constraint is `1 <= n <= 2^31 - 1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | `True` if the first player can force a win |
| Move | Remove `1`, `2`, or `3` stones |
| Winner | The player who removes the last stone |

Function shape:

```python
class Solution:
    def canWinNim(self, n: int) -> bool:
        ...
```

## Examples

For:

```python
n = 1
```

We take the only stone and win.

So the answer is:

```python
True
```

For:

```python
n = 2
```

We take both stones and win.

So the answer is:

```python
True
```

For:

```python
n = 3
```

We take all three stones and win.

So the answer is:

```python
True
```

For:

```python
n = 4
```

Whatever we take, the opponent can take the rest.

| We take | Stones left | Opponent takes |
|---:|---:|---:|
| `1` | `3` | `3` |
| `2` | `2` | `2` |
| `3` | `1` | `1` |

So the answer is:

```python
False
```

## First Thought: Dynamic Programming

We can define:

```python
dp[x]
```

as whether the current player can force a win with `x` stones remaining.

The base cases are:

```python
dp[1] = True
dp[2] = True
dp[3] = True
dp[4] = False
```

For a general `x`, the current player can win if they can make a move that leaves the opponent in a losing position.

So:

```python
dp[x] = (
    not dp[x - 1]
    or not dp[x - 2]
    or not dp[x - 3]
)
```

Code:

```python
class Solution:
    def canWinNim(self, n: int) -> bool:
        if n <= 3:
            return True

        dp = [False] * (n + 1)
        dp[1] = True
        dp[2] = True
        dp[3] = True

        for stones in range(4, n + 1):
            dp[stones] = (
                not dp[stones - 1]
                or not dp[stones - 2]
                or not dp[stones - 3]
            )

        return dp[n]
```

This works for small `n`.

## Problem With Dynamic Programming

The constraint allows `n` to be as large as:

```python
2^31 - 1
```

A DP array of that size is not practical.

We need to notice the pattern.

List the first few positions:

| Stones | Can current player win? | Reason |
|---:|---|---|
| `1` | `True` | Take `1` |
| `2` | `True` | Take `2` |
| `3` | `True` | Take `3` |
| `4` | `False` | Any move leaves `1`, `2`, or `3` |
| `5` | `True` | Take `1`, leave `4` |
| `6` | `True` | Take `2`, leave `4` |
| `7` | `True` | Take `3`, leave `4` |
| `8` | `False` | Any move leaves `5`, `6`, or `7` |

The losing positions are:

```python
4, 8, 12, 16, ...
```

These are exactly the multiples of `4`.

## Key Insight

If `n` is a multiple of `4`, the first player loses with optimal play.

Why?

If we start with:

```python
n = 4k
```

then whatever we take, it must be `1`, `2`, or `3`.

The opponent can take the complementary number to make the total removed in the round equal `4`.

| We take | Opponent takes | Total removed |
|---:|---:|---:|
| `1` | `3` | `4` |
| `2` | `2` | `4` |
| `3` | `1` | `4` |

So after every pair of turns, the heap loses exactly `4` stones.

Eventually, the opponent takes the last stone.

If `n` is not a multiple of `4`, we can remove:

```python
n % 4
```

stones on the first move.

That leaves a multiple of `4` for the opponent.

Then we use the same complementary strategy.

## Algorithm

Check whether `n` is divisible by `4`.

If yes, return `False`.

Otherwise, return `True`.

```python
return n % 4 != 0
```

## Correctness

If `n` is divisible by `4`, every possible first move removes `1`, `2`, or `3` stones and leaves a non-multiple of `4`.

The opponent can then remove enough stones so that the total removed across the two turns is `4`.

This returns the game to another multiple of `4`, but with fewer stones.

Repeating this strategy eventually leaves the first player with no winning move, and the opponent removes the last stone.

So multiples of `4` are losing positions.

If `n` is not divisible by `4`, the first player removes `n % 4` stones.

This leaves a multiple of `4` stones for the opponent.

From then on, whenever the opponent removes `x` stones, where `x` is `1`, `2`, or `3`, the first player removes `4 - x` stones.

Each pair of turns removes exactly `4` stones, and the first player eventually takes the last stone.

So non-multiples of `4` are winning positions.

Therefore the algorithm returns the correct result.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | One modulo operation |
| Space | `O(1)` | No extra data structure |

## Implementation

```python
class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0
```

## Code Explanation

The whole game reduces to this condition:

```python
n % 4 != 0
```

If the remainder is `0`, the first player starts from a losing position.

If the remainder is `1`, `2`, or `3`, the first player can remove that many stones and leave a multiple of `4`.

## Testing

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

    assert s.canWinNim(1) is True
    assert s.canWinNim(2) is True
    assert s.canWinNim(3) is True
    assert s.canWinNim(4) is False
    assert s.canWinNim(5) is True
    assert s.canWinNim(8) is False
    assert s.canWinNim(12) is False
    assert s.canWinNim(2**31 - 1) is True

    print("all tests passed")

test_can_win_nim()
```

Test meaning:

| Test | Why |
|---|---|
| `1`, `2`, `3` | First player can take all stones |
| `4` | Smallest losing position |
| `5` | First player leaves `4` |
| `8`, `12` | Larger losing positions |
| `2^31 - 1` | Large constraint value |