Skip to content

292. Nim Game

On LeetCode ->

Problem

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

The one who removes the last stone is the winner.

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 it 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.

Python solution

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

Comment on my solution

Not provided.