Nim Game: The Power of Modulo 4
LeetCode 292. Nim Game sets up a classic scenario. There is a pile of n stones on the table. Two players take turns removing 1, 2, or 3 stones. The player who takes the last stone wins. You always go first. Given n, can you guarantee a win?
At first glance, it feels like you need to simulate the game tree or use dynamic programming. But there is a beautiful pattern hiding in the math, and it reduces the entire problem to a single modulo check.
Finding the pattern
Start with the smallest cases and build up.
If n = 1, you take the one stone and win. Same for n = 2 (take two) and n = 3 (take three). You can always clear the pile in one move.
Now consider n = 4. You can take 1, 2, or 3, leaving your opponent with 3, 2, or 1 stones respectively. In every case, your opponent faces a pile they can clear in one move. No matter what you do, you lose.
What about n = 5? Take 1 stone, and your opponent faces 4. We just established that whoever faces 4 stones loses. So you win by forcing that position on them. The same logic works for n = 6 (take 2, opponent gets 4) and n = 7 (take 3, opponent gets 4).
At n = 8, the cycle repeats. Whatever you take (1, 2, or 3), your opponent can always respond by taking enough to drop the total by exactly 4. They leave you with 4 stones, and you are stuck in the losing position again.
The pattern is clear: you lose exactly when n % 4 == 0. Every multiple of 4 is a losing position. Everything else is a winning position.
The one-line solution
def canWinNim(n: int) -> bool:
return n % 4 != 0
Why does this work? Think about the invariant. If n is not a multiple of 4, you can always take n % 4 stones on your first move, leaving your opponent with a multiple of 4. From that point on, whatever your opponent takes (call it k, where 1 <= k <= 3), you take 4 - k. This keeps the pile at a multiple of 4 after every pair of turns. Eventually the pile hits 4, then 0 on your turn. You took the last stones.
If n is a multiple of 4, the roles reverse. Your opponent uses the same strategy against you, and there is nothing you can do to escape.
Step-by-step walkthrough
Step 1: n = 1, 2, or 3. Take all the stones and win.
When the pile has 1 to 3 stones, you grab everything on your first turn. Game over.
Step 2: n = 4. No matter what you take, your opponent wins.
Take 1, opponent takes 3. Take 2, opponent takes 2. Take 3, opponent takes 1. They always grab the last stone.
Step 3: n = 5. Take 1 stone, leaving your opponent with 4.
You force your opponent into the losing position. They face n=4, and we just showed that is unwinnable.
Step 4: n = 8. Whatever you take, your opponent leaves you with 4.
Take k stones (1, 2, or 3). Your opponent takes 4-k. The pile drops from 8 to 4, and now you face the losing position.
Step 5: The pattern. You lose if and only if n % 4 == 0.
Every group of 4 repeats: win, win, win, lose. The player who can force n % 4 == 0 on their opponent always wins.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Modulo check | O(1) | O(1) |
| Dynamic programming | O(n) | O(n) |
| Game tree | O(3^n) | O(n) |
The modulo solution runs in constant time and uses no extra memory. A DP approach would build a table of win/lose states from 1 to n, which works but is wildly overkill. A brute-force game tree explores every possible sequence of moves and is exponential. The math gives you the answer instantly.
The building blocks
Invariant-based game theory
The core idea here is maintaining an invariant across turns. You choose a move that puts your opponent into a losing state, and then mirror their moves to preserve that property. This same reasoning appears in many combinatorial game theory problems. Whenever you see a two-player game with optimal play, look for positions that are inherently winning or losing, and figure out the transitions between them.
Modular arithmetic patterns
Recognizing that a problem has periodic behavior and expressing it with modulo is a powerful tool. In this case, the period is 4 because the maximum move size is 3 (and 3 + 1 = 4). If the rules allowed taking 1 to k stones, the losing positions would be multiples of k + 1. Spotting this generalization helps you solve entire families of problems, not just one.
Edge cases
- n = 1: You take the single stone and win.
1 % 4 = 1, which is not zero, so the function returnsTrue. - n = 4: The smallest losing position. No matter which move you make, your opponent clears the rest.
4 % 4 = 0, returnsFalse. - Very large n: The modulo check is O(1) regardless of how big
ngets. Evenn = 10^9returns instantly. - n = 0: Not part of the LeetCode constraints (n is at least 1), but if you did check,
0 % 4 = 0returnsFalse, which makes sense because there are no stones to take.
The Nim Game is a special case of a broader family called "subtraction games." If each player can take 1 to k stones, the losing positions are all multiples of k+1. The Sprague-Grundy theorem generalizes this further to handle arbitrary move sets and multi-pile variants.
From understanding to recall
The Nim Game solution is just one line of code, but what makes it stick is understanding why that line works. The chain of reasoning from small cases to the modulo invariant is the real skill. Next time you see a game theory problem, you will know to look for periodic patterns and invariant-based strategies.
Spaced repetition helps you internalize that reasoning. CodeBricks drills the building blocks (modular arithmetic, game state analysis) independently, so when they appear together in a new problem, you recognize both pieces without hesitation.
Related posts
- Power of Two - Another problem solved with a single mathematical check, recognizing a structural property of the input
- Happy Number - Detecting patterns in number sequences, building intuition from small cases first
- Climbing Stairs - Building optimal solutions from smaller subproblems, the same bottom-up reasoning that reveals the mod 4 pattern here