292. Nim Game

Reformulated question¶

Given n stones, two players alternate removing 1 to 3 stones, and you play first.

Return whether the first player can force a win if both play optimally.

Example:

n = 4 -> False
Why: any move leaves 1, 2, or 3 stones, so opponent takes all and wins.

Key trick¶

The losing positions are exactly multiples of 4.

• If n % 4 == 0, every move gives the opponent a non-multiple of 4.
• If n % 4 != 0, remove n % 4 stones to leave a multiple of 4.

Trap¶

• Overthinking with DP or recursion when the pattern is constant-time.
• Forgetting "both play optimally", which is what makes the modulo pattern valid.
• Off-by-one on small cases like n = 1, 2, 3, 4.

Why is this question interesting?¶

It looks like DP, but collapses to a simple invariant.

• Good interview signal for spotting patterns from small states.
• Tests whether you can turn recurrence into a math observation.

Solution with idiomatic Python¶

class Solution:
    def canWinNim(self, n: int) -> bool:
        # Multiples of 4 are losing states.
        # Any other number can move to a multiple of 4.
        return n % 4 != 0

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("n", "expected"),
    [
        (1, True),
        (2, True),
        (3, True),
        (4, False),
        (5, True),
        (6, True),
        (7, True),
        (8, False),
        (12, False),
        (15, True),
        (16, False),
        (1348820612, False),
        (2147483647, True),
    ],
)
def test_canWinNim(n, expected):
    assert Solution().canWinNim(n) is expected

Comment my solution¶

No solution was provided.