Nim Game

Nim Game

What is this problem about?

The Nim Game is a classic combinatorial game theory problem. Two players alternate turns removing 1, 2, or 3 stones from a pile. The player who takes the last stone wins. You go first. Determine if you can guarantee a win given n stones. This Nim Game coding problem has a beautifully simple mathematical solution based on game theory.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this as a test of mathematical game theory reasoning. The answer — you lose if and only if n is divisible by 4 — follows from analyzing small cases and recognizing the periodic pattern. The brainteaser, math, and game theory interview pattern is directly demonstrated.

Algorithmic pattern used

Mathematical observation (modulo 4). If n % 4 == 0, the second player always wins with optimal play — whatever you take (1, 2, or 3), your opponent takes enough to leave you with another multiple of 4. Otherwise, you can always take n % 4 stones on your first turn, leaving a multiple of 4 for your opponent, guaranteeing your win. Answer: return n % 4 != 0.

Example explanation

n=4: any move (1,2,3) leaves 3,2,1 stones for opponent. Opponent takes all and wins. You lose. n=5: take 1 → leave 4 for opponent. Opponent is in the losing position. You win. n=8: any move leaves 7,6,5 → opponent takes 3,2,1 → leaves 4 for you → you lose. Lose. n=9: take 1 → leave 8 (mult of 4) for opponent. Win.

Common mistakes candidates make

• Using DP to compute win/loss for each n (correct but O(n) when O(1) suffices).
• Not recognizing the period-4 pattern from the base cases.
• Implementing game tree search (far too slow for large n).
• Returning true for n=4 (you cannot win when n=4 with optimal opponent play).

Interview preparation tip

Game theory problems in interviews often have elegant closed-form solutions based on pattern recognition. Always analyze the base cases first: n=1 (win), n=2 (win), n=3 (win), n=4 (lose), n=5 (win)... The period-4 losing positions reveal the n % 4 == 0 rule. Practice recognizing this modular structure in other Nim variants: "remove 1 to k stones," "take from multiple piles" (XOR-based Sprague-Grundy). These game theory patterns appear across Bloomberg, Google, and Microsoft interview rounds.