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:

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

Function shape:

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

Examples

For:

n = 1

We take the only stone and win.

So the answer is:

True

For:

n = 2

We take both stones and win.

So the answer is:

True

For:

n = 3

We take all three stones and win.

So the answer is:

True

For:

n = 4

Whatever we take, the opponent can take the rest.

So the answer is:

False

First Thought: Dynamic Programming

We can define:

dp[x]

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

The base cases are:

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:

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

Code:

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:

2^31 - 1

A DP array of that size is not practical.

We need to notice the pattern.

List the first few positions:

The losing positions are:

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:

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.

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:

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.

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

Implementation

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

Code Explanation

The whole game reduces to this condition:

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

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: