Nim Game & XOR Strategy — The Foundation of Combinatorial Games
🤔 Why Nim Matters: The Universal Game Solver
Imagine you're given a game with multiple piles of stones. On each turn, a player removes any positive number of stones from a single pile. The player who takes the last stone wins. Sounds simple, right?
Here's the mind-blowing part: This game — Nim — is the FOUNDATION of ALL impartial combinatorial games. Thanks to the Sprague–Grundy theorem, EVERY impartial game (Chess variants excluded since they're not impartial) is equivalent to a game of Nim! If you understand Nim, you understand game theory at its core.
This is NOT just theory — Nim problems appear in Amazon, Google, Meta interviews, and are the #1 topic in competitive programming game theory sections (Codeforces, AtCoder, CSES, LeetCode Hard).
Tip
💡 The Key Insight: Nim uses XOR (⊕) as its secret weapon. The XOR of all pile sizes — called the Nim-sum — determines whether a position is winning or losing. This is Bouton's Theorem, discovered in 1901, and it's STILL the basis of modern combinatorial game theory.
1. Nim — The Foundation
Rules of Standard Nim (Normal Play):
We have n piles of stones, each with some number of stones
On your turn, choose one pile and remove any positive number of stones from it
You can take all stones from a pile, some, or just one — as long as it's at least 1
The player who takes the last stone wins (normal play convention)
Both players play optimally — no mistakes allowed
🤔 Think Like Aditya Verma — The "Choose/Not-Choose" Pattern
Here's how we frame Nim decisions recursively:
Let's visualize a typical Nim state:
Bouton's Theorem — The Complete Theorem
Charles L. Bouton (1901) proved that a Nim position is:
Losing (P-position): Nim-sum (XOR of all pile sizes) = 0
Winning (N-position): Nim-sum ≠ 0
From a winning position (Nim-sum ≠ 0), there is ALWAYS a move that makes Nim-sum = 0. From a losing position (Nim-sum = 0), EVERY move makes Nim-sum ≠ 0.
Warning
⚠️ Common Misconception: "Losing position means I'll definitely lose." No — it means that if your OPPONENT plays optimally, you WILL lose. But if they make a mistake (make Nim-sum non-zero), you can immediately flip it back and win. Never give up from a losing position — look for opponent errors!
The Winning Move Algorithm
When you see Nim-sum ≠ 0, here's how to find the winning move:
ProblemEmbed: game-of-nim
ProblemEmbed: nim-game-cses
ProblemEmbed: intro-nim
2. XOR Strategy (Nim-sum) — Deep Intuition
Let's REALLY understand WHY Nim-sum = 0 means losing. Not just memorize the formula.
Binary Level Intuition
Think of each pile's size in binary. XOR checks whether each bit position appears an ODD number of times across all piles. If a bit appears an odd number of times, the XOR has that bit set.
The "Make It 0" Strategy — Striver Style
The Golden Rule: "If XOR is non-zero, I can ALWAYS make it zero in one move. If XOR is zero, ANY move I make will make it non-zero."
Key Insight
🔑 Why XOR and not sum? XOR captures the PARITY of each bit position. Sum would capture magnitude, but Nim is about balanced/unbalanced binary columns. A pile of 8 stones (1000) can balance a pile of 4 (0100) + 2 (0010) + 1 (0001) + 1 (0001) in XOR sense, but sum-wise 8 ≠ 4+2+1+1=8... Indeed they're equal! But that's coincidence. The XOR approach generalizes because it captures position-level parity — the essence of "do I have a counter for every bit?"
Tech DOSE — Edge Cases & Gotchas
Edge Case 1: Empty Piles
If a pile has 0 stones, it contributes nothing to XOR (0 ^ x = x). Empty piles can be ignored — they don't affect the game state.
Edge Case 2: Single Pile
With one pile of n stones: Nim-sum = n (since 0 ^ n = n). If n > 0, Nim-sum ≠ 0 → WINNING. Remove all stones → win immediately. Simple, but confirms the theorem works.
Edge Case 3: All Piles = 1
If every pile has exactly 1 stone, Nim-sum = (n mod 2) where n = number of piles. If n is odd, Nim-sum = 1 → winning. If n is even, Nim-sum = 0 → losing. This matches our intuition: with all piles of size 1, the game becomes "who takes the last stone" — players alternate taking one stone per turn. First player wins with odd count.
Edge Case 4: Large Piles
Nim works for ANY non-negative integers. Pile sizes can be up to 10^9, 10^18, or even larger. JavaScript's bitwise XOR works on 32-bit signed integers, but for competitive programming, use BigInt or language with 64-bit XOR (C++, Java, Python).
Warning
⚠️ JavaScript Limitation:^ in JavaScript works on 32-bit signed integers. For values above 2^31 - 1, use BigInt:BigInt(a) ^ BigInt(b) and convert back. In Python, XOR works on arbitrary precision integers natively.
3. Staircase Nim — Nim on a Staircase
Rule variation: There are n stairs (indexed 0 to n-1). Each stair has some stones. A move consists of moving any positive number of stones from stair i to stair i-1 (down one step). Stair 0 is the "ground" — stones removed from stair 0 are taken out of the game. The player who moves the last stone to ground wins.
🤔 Think About It
This seems different from Nim — we're moving stones, not removing them. But the Sprague–Grundy theorem says this is equivalent to something simpler...
The Key Insight
Staircase Nim is equivalent to standard Nim played on the ODD-indexed stairs!
Intuition
Stones on even-indexed stairs (0, 2, 4, ...) are "safe" — if your opponent moves stones from an even stair to an odd stair, you can immediately move them further down (odd → even). This gives the opponent no net advantage. The critical stones are those on odd-indexed stairs — they're the ones that actually reach the ground.
Tip
⚡ Interview Tip: When you see "move stones left/down" in a game, think about PARITY of indices. Staircase Nim is a classic example where the reduction seems non-trivial, but the answer is elegant. Say this in interviews: "Staircase Nim reduces to XOR of odd-position piles."
4. Misère Nim — When Last Move LOSES
Rule variation: Same rules as standard Nim, EXCEPT the player who takes the LAST stone LOSES. This changes EVERYTHING.
The Misère Twist
For most impartial games, normal and misère play have vastly different solutions. Nim is special — the solution is almost identical, with ONE exception:
Misère Nim Strategy
Key Insight
🔑 Misère Nim Insight: The only difference is when ALL piles have size ≤ 1. In that case, normal-play says "odd count of 1s wins" but misère says "odd count of 1s LOSES" (because you DON'T want to take the last stone). If any pile > 1 exists, the strategy is the SAME as normal Nim!
Tech DOSE — Misère Edge Cases
All piles = 1: XOR of all 1s. If even count → normal play loses, misère WINS (opponent takes last). If odd count → normal play wins, misère LOSES (you take last).
One pile ≥ 2, rest 1s: Normal Nim strategy applies. Make a move that leaves odd number of size-1 piles.
Multiple piles ≥ 2: Identical to normal Nim. Just aim for Nim-sum = 0.
Empty game (all zeros): First player already lost (no moves). In misère, also a loss.
5. Tower Breakers & Variants
Tower Breakers is a Nim VARIANT that appears frequently in competitive programming (HackerRank, LeetCode). Let's solve it using the "At each move, I choose/not-choose" pattern.
Problem Statement (Standard)
There are n towers, each initially of height m. On each move, a player chooses a tower and reduces its height to a divisorof its current height (strictly smaller than current height). The player who makes the last valid move wins. Both players play optimally.
🤔 Think About It — "Each tower, I choose or not-choose"
Let's apply Aditya Verma's thinking:
Mathematical Analysis
For Tower Breakers with n towers all of height m:
Tower Breakers Again (Strike Back)
In this harder variant, towers can have different heights. The game is no longer symmetric analysis — we need the full Nim-sum approach.
Warning
⚠️ Important Distinction: Tower Breakers (equal heights) and Tower Breakers Again (different heights) have DIFFERENT solutions. The first uses simple parity. The second uses XOR of Grundy values where each tower's Grundy is determined by its parity (for this specific problem's move rules). ALWAYS check which variant you're solving!
ProblemEmbed: tower-breakers
ProblemEmbed: tower-breakers-again
6. Sequential Nim — Forced Order Play
Sequential Nim adds a twist: players MUST take stones from the first NON-EMPTY pile. You cannot skip to a later pile until all earlier piles are empty.
🤔 Think About It
This is NOT standard Nim anymore! The XOR strategy doesn't apply directly because the "choose any pile" constraint is gone. Instead, the game is about WHO CONTROLS the first pile with more than 1 stone.
Aditya Verma approach — "At each pile, I choose: take 1 stone (forced) OR take all stones (seize control)?"
Tech DOSE — Sequential Nim Edge Cases
All piles = 1: No choices at all. Players just alternate taking one stone. If length is odd → P1 wins (takes last). Even → P2 wins.
First pile already > 1: P1 immediately has control. P1 wins regardless of remaining piles.
Single pile: If size = 1 → P1 takes it, game over, P1 wins. If size > 1 → P1 takes all but 1 (or takes all) → P1 wins.
Large >1 pile early but later forced losses: The player who controls the first >1 pile can dictate the entire game — they can always force a win by leaving exactly 1 stone in that pile after their move, ensuring they keep turn parity advantage.
ProblemEmbed: sequential-nim
🎯 Interview Cheat Sheet
Key Insight
Q1: When do I use Nim-sum vs. DP vs. Grundy numbers? Nim-sum (XOR): Game is the sum of independent piles, each move affects exactly one pile, no additional constraints. DP/minimax: Game state is small enough to enumerate, or there's a single pile with complex rules. Grundy numbers: Game can be split into independent sub-games with different rules (the general Sprague–Grundy approach).
Key Insight
Q2: How do I spot a Nim problem in an interview? Keywords: "piles of stones", "take any number from one pile", "last move wins", "optimal play". If the problem says "multiple piles, choose one, remove some", it's 90% Nim. Even if the removal rule changes (remove 1-3 stones, remove perfect squares), the core Nim framework often applies via Grundy numbers.
Key Insight
Q3: What's the difference between normal and misère Nim again? Normal: last move WINS. Misère: last move LOSES. The ONLY difference in strategy is when all piles ≤ 1. Otherwise, they're identical. Remember: if any pile > 1, use normal Nim strategy for both.
Key Insight
Q4: What if I can remove stones from MULTIPLE piles in one move? That's a different game entirely! If you can touch more than one pile per turn, the XOR analysis breaks. The game becomes Wythoff's Nim or similar, which needs different techniques (Beatty sequences, golden ratio for Wythoff).
Key Insight
Q5: How do I handle large constraints (pile sizes up to 10^18)? XOR is O(1) per pile regardless of size. The number of piles (n) dominates. So for n ≤ 10^5, the O(n) solution is fine. But beware of language limitations: JS 32-bit XOR, Python unlimited, C++ needs 64-bit (long long).
Key Insight
Q6: "At each pile, I either take some stones or pass" — when does this thinking help? This recursive framing (Aditya Verma style) helps when the game has ADDITIONAL restrictions. Like "you can take at most k stones per pile" or "you must take stones from the first non-empty pile" (Sequential Nim). For standard Nim, the XOR formula IS the closed-form solution of this recursion.
📝 Key Takeaways
Nim-sum = XOR of all pile sizes — it's 0 when losing, ≠ 0 when winning
From Nim-sum ≠ 0, ALWAYS find a winning move: pick a pile where (pile XOR nimSum) < pile, reduce it to that value
Normal vs. Misère: Identical except when ALL piles ≤ 1 — then normal = parity wins, misère = parity loses
Staircase Nim = XOR of odd-indexed piles — even-indexed piles are "mirrored" and cancel out
Tower Breakers (equal heights): If m=1 → P2 wins; else parity of n decides winner
Tower Breakers Again (different heights): XOR of Grundy values — each tower's Grundy depends on parity for this game
Sequential Nim: First pile with >1 stones determines the winner (based on who reaches it)
Sprague–Grundy theorem: EVERY impartial game is equivalent to a Nim heap — learn Nim, learn them all
Time: O(n), Space: O(1) — Nim solutions are almost always linear time and constant space
Practice! — The Playground below has 6 problems. Each reinforces a different Nim concept. Start with "Game of Nim" (basic), then "Tower Breakers" (variant), finally "Sequential Nim" (forced order).
Note
🔮 What's Next? You've mastered Nim basics! Move to Advanced Nim & Variants to learn Grundy numbers, impartial games, and the full Sprague–Grundy theorem.
// At each pile "i", I have a CHOICE:// OPTION 1: Take some stones from THIS pile (reduce it to any smaller size)// OPTION 2: Skip this pile, move to the next oneBut wait — Nim is NOT sequential. I pick ANY pile each turn.So the choice is: "From the CURRENT state (piles[]), I choose one pile, and reduce it to any lesser value. If I can make XOR = 0, opponent loses."This is the "At each move, I either:" pattern → Pick pile with most significant bit in nim-sum → Reduce it to (pile XOR nim-sum) → This forces nim-sum to 0 → opponent in losing position
function findWinningMove(piles) { const nimSum = piles.reduce((a, b) => a ^ b, 0); if (nimSum === 0) return null; // Losing position, no winning move for (let i = 0; i < piles.length; i++) { const target = piles[i] ^ nimSum; if (target < piles[i]) { // We can reduce pile[i] to target! const remove = piles[i] - target; return { pile: i, remove, newSize: target }; } } return null; // Should never happen for nimSum !== 0}// Example: piles = [3, 5, 4]// nimSum = 3 ^ 5 ^ 4 = 2// For pile 0 (3): target = 3 ^ 2 = 1, 1 < 3 → remove 2 stones from pile 0// New state: [1, 5, 4] → nimSum = 1 ^ 5 ^ 4 = 0 → opponent LOSES
Consider piles: [3, 5, 4]Binary: 3 = 011 5 = 101 4 = 100 --------XOR = 010 = 2Bit 0 (1's place): 1 + 1 + 0 = 2 (even) → 0Bit 1 (2's place): 1 + 0 + 0 = 1 (odd) → 1 ← THIS is the imbalance!Bit 2 (4's place): 0 + 1 + 1 = 2 (even) → 0Goal: Make every bit position have EVEN count → XOR = 0
// Staircase Nim — Solutionfunction staircaseNim(stairs) { // XOR only the ODD-indexed stairs (1-indexed: odd positions) // In 0-indexed arrays: stairs[1], stairs[3], stairs[5], ... let xorSum = 0; for (let i = 1; i < stairs.length; i += 2) { xorSum ^= stairs[i]; } return xorSum !== 0 ? "First" : "Second";}// Why? Because even-indexed moves can be "mirrored" by opponent.// The real game happens on odd-indexed stairs — that's where the// imbalance matters.
function misereNim(piles) { const allOnes = piles.every(p => p <= 1); if (allOnes) { // Special case: all piles are 0 or 1 // XOR of all pile sizes (not nim-sum logic!) const xorAll = piles.reduce((a, b) => a ^ b, 0); return xorAll === 0 ? "First" : "Second"; } else { // Normal Nim strategy applies! const nimSum = piles.reduce((a, b) => a ^ b, 0); return nimSum !== 0 ? "First" : "Second"; }}// Why? In misère play, you want to FORCE opponent to take last stone.// When ALL piles are 1, the player who controls parity wins.// If any pile > 1 exists, use normal Nim strategy but set final move// to leave last pile at 1 (not 0) — forcing opponent to take it.
// For each tower of height h, the AVAILABLE MOVES are:// All divisors d of h where d < h// So if h = 6, moves are: 1, 2, 3 (divisors of 6 that are < 6)// If h = 1, NO moves (1 has no divisor < 1)// The game is IMPARTIAL — same moves for both players// Each tower is INDEPENDENT — a move on tower A doesn't affect B// Total game = XOR of Grundy numbers of each tower// But there's an even simpler analysis for equal-height towers...
function towerBreakers(n, m) { // Case 1: m = 1 → no moves possible → P1 loses if (m === 1) return 2; // Player 2 wins // Case 2: n is odd → P1 wins (by symmetry-breaking strategy) // Case 3: n is even → P2 wins (P1's move can be mirrored) return n % 2 === 1 ? 1 : 2;}// Intuition:// - If all towers = 1, nobody can move → P1 loses immediately// - If m > 1, the first player can reduce ONE tower to 1 on first move// - Now we have (n-1) towers at m, 1 tower at 1// - If n is odd, (n-1) is even → P2 faces symmetric game → P1 wins// - If n is even, (n-1) is odd → P2 mirrors P1's moves → P1 loses
// Tower Breakers Again — General Case// Each tower is an independent sub-game// Grundy number for a tower = number of proper divisors - 1? No...// Actually: Grundy(h) = mex of Grundy values of all reachable states// But for this specific problem, we can use a simpler insight:function towerBreakersAgain(heights) { // A tower of height h contributes: // - 0 if h is even (can be "paired" by opponent) // - 1 if h is odd (creates imbalance) // Wait, that's the simplified version. Let's be rigorous: // For each tower, the Grundy number is the XOR of Grundy of its divisors. // But there's a pattern: Grundy(h) = 0 if h is 1 or even? No... // The ACTUAL solution: Count odd-height towers let oddCount = heights.filter(h => h % 2 === 1).length; // If odd count is odd → XOR ≠ 0 → First wins // If odd count is even → XOR = 0 → Second wins return oddCount % 2 === 1 ? "First" : "Second";}// Wait — let me verify this logic more carefully...// For Tower Breakers (equal heights): answer based on n parity and m// For Tower Breakers Again (different heights): it's about odd-height towers count// Because: Grundy(even) = 0, Grundy(odd) = 1 (for THIS specific game rules)
// Sequential Nim — Solutionfunction sequentialNim(piles) { const n = piles.length; // Find the first pile that is NOT 1 for (let i = 0; i < n; i++) { if (piles[i] > 1) { // Found first >1 pile at index i // If i is even (0-indexed) → i+1 moves already made // i even → P1's turn when reaching this pile → P1 wins // i odd → P2's turn when reaching this pile → P2 wins return i % 2 === 0 ? "First" : "Second"; } } // All piles are 1 — parity decides return n % 2 === 0 ? "Second" : "First";}// Intuition:// - If a pile has 1 stone, there's no CHOICE — take it (forced move)// - The first pile with >1 stone gives CONTROL// - The player who reaches it can decide the entire rest of the game// - They take (size - 1) stones, leaving 1 for opponent → they control parity