Nim and the Grundy Number
Solve impartial games with XOR.
Nim and the Grundy Number is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Meet the Game of Nim
In Nim there are several piles of stones. On your turn you remove any number from one pile, and the player who takes the last stone wins. 🪨
The Magic Quantity: XOR
The whole game is decided by the XOR of all pile sizes. That single number tells you who is winning.
The Nim-Sum Rule
If the XOR of the piles, called the nim-sum, is zero, the player to move loses. If it is non-zero, that player wins.
piles = [3, 4, 5]
nim_sum = 0
for p in piles:
nim_sum ^= pWhy Zero Means Trouble
From a zero nim-sum every move breaks the balance, handing your opponent a non-zero sum that they can always restore.
Finding the Winning Move
When the nim-sum is non-zero, there is always a move that drives it back to zero. That move puts your opponent in the losing seat.
Beyond Nim: Grundy Numbers
For other impartial games we use a Grundy number per state. It generalizes the nim-sum idea to almost any take-away game.
The mex Operation
A state's Grundy value is the mex: the smallest non-negative integer missing from the Grundy values of its moves.
def mex(s):
i = 0
while i in s:
i += 1
return iCompute Grundy by Recursion
Recurse into all reachable states, collect their Grundy values, then take the mex of that set.
def grundy(n):
return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})Grundy Zero Is a Loss
A single game state with Grundy 0 is a losing position, exactly like a nim-sum of zero. Non-zero means a win.
The Sprague-Grundy Theorem
For independent games played at once, XOR their Grundy numbers. This Sprague-Grundy result turns any sum of games into Nim. ✨
When It Applies
Grundy theory needs an impartial game: both players have the same moves and the last to move wins. Check that before using it.
Quick Check
You start a Nim game with piles 1, 2, and 3. Are you winning?
Recap
Nim hinges on the XOR of piles: zero loses, non-zero wins. Grundy numbers and mex extend this to many impartial games. 🏆
Frequently asked questions
Is the “Nim and the Grundy Number” lesson free?
Yes — the full text of “Nim and the Grundy Number” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Nim and the Grundy Number”?
Solve impartial games with XOR. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Nim and the Grundy Number” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Winning & Losing States in Games
- Nim and the Grundy Number
- Meet in the Middle
- Debug Fast: Stress Tests & Triage