Imagine you're at a party with a bowl of 7 matchsticks. You and a friend take turns removing 1, 2, or 3 matchsticks. The player who takes the LAST matchstick wins.
Your friend says: "Go first, I dare you."
Should you accept? Is this a fair game? Or has your friend just tricked you into a losing position?
Spoiler: If you know the pattern, you ALWAYS win — no matter what your opponent does. The same pattern appears in Amazon, Google, and Meta interviews. And it's NOT about complex math — it's about seeing the modulo magic.
Let's start with the most fundamental principle that governs ALL two-player deterministic games:
Tip
💡 The Golden Rule: A position is winning if there EXISTS a move to a losing position. A position is losing if ALL moves go to a winning position. This recursive definition is the ENGINE behind every game DP!
1. Divisor Game — Even/Odd Magic
Problem (Leetcode 1025): Alice and Bob take turns playing a game. Given N, on each turn:
Choose any x where 0 < x < N and N % x === 0
Replace N with N - x
Player who CANNOT make a move loses
Alice goes first. Return true if Alice wins.
🤔 Let's Think About It — The Party Analogy
Imagine you and a friend have a pile of N cookies. On each turn, you must eat a divisor-count of cookies (you can eat 1, or any number that divides the current pile evenly). The person who CANNOT eat (because N=1 and the only divisor is 1 which is not less than N) loses.
Let's trace through small values to see the pattern:
Brute Force — DP Approach
Let's solve it the straightforward way first. We'll build a DP table from 1 to N:
✅ This works! But it's O(N²). Can we do better?
✨ The Optimal — Number Theory Pattern
Look at our DP table again. What do you notice?
N
1
2
3
4
5
6
7
8
9
10
Winner
Loss
Win
Loss
Win
Loss
Win
Loss
Win
Loss
Win
Even N → Alice wins. Odd N → Alice loses. That's it!
Why? The key is that 1 is a divisor of every number. So from any N, you can always subtract 1. But that doesn't mean you should!
Key Insight
🔑 The Intuition: From an even N, Alice can subtract 1 → N becomes odd. From an odd N, the only divisors are odd (odd × something = odd, so divisor is odd). Odd - odd = even. So: • Even N → Alice can force Bob into an odd (losing) position • Odd N → Bob always gets an even (winning) position Base case: N=1 is odd and losing. This cascades up!
Edge Cases
N = 1? No divisor x where 0 < x < 1 → Alice loses.
N = 2? Pick x=1 → Bob gets N=1 (losing) → Alice wins.
N = 0? Not in problem constraints (N ≥ 1).
Large N (10³)? O(1) solution works instantly.
ProblemEmbed: divisor-game
2. Elimination Game — The Recursive Formula
Problem (Leetcode 390): You have a list of numbers from 1 to n. First, eliminate all numbers from left to right (remove 1st, 3rd, 5th...). Then, eliminate from right to left on the remaining. Repeat alternating directions until one number remains. Return it.
🤔 The Party Analogy
Imagine a line of friends numbered 1 to n. First pass: you kick out every other friend starting from the left. Second pass: you kick out every other friend starting from the right. Keep alternating. Who's the last person standing?
Brute Force — Simulation
✅ Works! But O(n) space and O(n log n) time. With n up to 10⁹, this won't fly.
✨ The Optimal — Recursive Pattern
Let's find a formula. Let f(n) be the last remaining number when starting left-to-right. And g(n) be the last remaining when starting right-to-left.
Key observation: After one left-to-right pass, we keep only the even-indexed numbers (1-indexed), which are 2, 4, 6, ..., 2×⌊n/2⌋. These are exactly 2 × [1, 2, 3, ..., ⌊n/2⌋].
But now the direction flips! So the problem becomes:
Key Insight
🔑 The Intuition: After one pass, the remaining numbers are always2 × [1, 2, ..., k]. The subproblem is f(k)with flipped direction. The formula 2 × (1 + n/2 - f(n/2))elegantly handles the direction flip without needing a separate g(n) function.
Dry Run — See the Recursion Unfold
n
floor(n/2)
f(floor(n/2))
1 + n/2 - f(n/2)
2 × result
1
—
—
—
1
2
1
1
1 + 1 - 1 = 1
2
3
1
1
1 + 1 - 1 = 1
2
4
2
2
1 + 2 - 2 = 1
2
5
2
2
1 + 2 - 2 = 1
2
6
3
2
1 + 3 - 2 = 2
4
7
3
2
1 + 3 - 2 = 2
4
8
4
2
1 + 4 - 3 = 2
6
9
4
2
1 + 4 - 2 = 3
6
Edge Cases
n = 1? Return 1 immediately (no elimination needed).
n = 2? Left→Right eliminates 1 → only 2 remains.
n = 0? Not in constraints (n ≥ 1).
n = 10⁹? O(log n) recursion — only ~30 recursive calls!
ProblemEmbed: elimination-game
ProblemEmbed: game-with-integers
3. Subtraction Games — The Take-Away Pattern
Problem: There are N stones in a pile. Each player can take 1, 2, or 3 stones on their turn. The player who takes the LAST stone wins. Alice goes first — can she win?
🤔 The Party Analogy
Remember the matchstick party problem from the intro? This is EXACTLY it! You have N matchsticks. Each turn, you take 1-3. Take the last one and you win.
Pattern: If N % 4 === 0, you lose. Otherwise you win.
Key Insight
🔑 Why? If you're at N % 4 === 0, no matter what you take (1-3), your opponent gets N % 4 !== 0. From there, they can ALWAYS take the right amount to bring it back to a multiple of 4. Eventually you get stuck at 4 and can only leave 1-3 for your opponent to take and win!
Generalization: Take 1 to K Stones
The pattern extends: if you can take 1 to K stones, then N % (K+1) === 0 is the losing position.
📊 Dry Run — N=7, Take 1-3
N
dp[N]
Can move to?
Explanation
0
False
—
No stones left → lose
1
True
Take 1 → dp[0]=False
Take all → win
2
True
Take 2 → dp[0]=False
Take all → win
3
True
Take 3 → dp[0]=False
Take all → win
4
False
Take 1→dp[3]=T, 2→dp[2]=T, 3→dp[1]=T
All moves go to winning positions → lose
5
True
Take 1 → dp[4]=False
Move to 4 (losing) → win!
6
True
Take 2 → dp[4]=False
Move to 4 (losing) → win!
7
True
Take 3 → dp[4]=False
Move to 4 (losing) → win!
Edge Cases
N = 0? No stones to take → false (but N ≥ 1 usually).
N huge (10⁹)? O(1) check — instant!
K = 1? Only take 1. N % 2 === 0 → even N loses.
Arbitrary moves set ([1, 3, 4])? Can't use simple modulo — need DP.
Warning
⚠️ General Moves Set: If the allowed moves are NOT consecutive integers (e.g., [1, 3, 4]), the simple modulo pattern breaks. You MUST use DP for arbitrary move sets. The pattern N % (K+1) only works when you can take 1 through K stones consecutively.
ProblemEmbed: subtraction-game-1
ProblemEmbed: buttons
ProblemEmbed: a-game-with-stones
ProblemEmbed: game-of-matchsticks
ProblemEmbed: removal-game-gfg
ProblemEmbed: game-of-chips
ProblemEmbed: take-away-game
ProblemEmbed: winner-stick-cutting
4. Brainteaser Patterns — Think Like a Strategist
Now that we've mastered the core patterns, let's explore some variations that appear in interviews. These look different on the surface but use the SAME underlying game theory principles.
Valid Tic-Tac-Toe State
Problem (Leetcode 794): Given a Tic-Tac-Toe board, determine if it represents a reachable game state.
This isn't a "who wins" problem — it's about recognizing valid board configurations given the turn order.
Key Insight
🔑 Strategy: The game state validation uses simple counting rules: • X goes first → count_X = count_O or count_X = count_O + 1 • Only one player can win at a time • If X wins → X must have played one extra turn • If O wins → counts must be equal (O just played last)
Game of Stairs — The Parity Trick
Problem: Two players move a token on a staircase. On each turn, a player moves the token down 1, 2, or 3 steps. The player who reaches step 0 wins.
Wait — this is just our subtraction game in disguise! The staircase is just a visual wrapper around the same N-stones problem. The token's position is the number of stones remaining. The moves are the same (1-3 steps down). The winning condition is the same (reach 0).
This is a KEY insight for interviews: many problems are isomorphic — they LOOK different but are mathematically identical. Once you recognize the core pattern, you can apply the same solution.
ProblemEmbed: game-of-stairs
ProblemEmbed: game-with-numbers
ProblemEmbed: valid-tic-tac-toe-state
🎯 Interview Cheat Sheet
Key Insight
Q1: How do I identify a "game" problem in an interview? Keywords: "two players", "alternate turns", "optimal play", "who wins?", "can the first player win?". If you hear these, it's a game theory problem.
Key Insight
Q2: What's the FIRST thing I should try? Brute-force DP on small values (N=0 to ~20). Build the DP table. LOOK for a pattern. Most game problems have a simple number theory answer hiding behind the DP.
Key Insight
Q3: What are the common patterns I should memorize? Divisor Game: Even N → Win. Odd N → Lose. Elimination Game: Recursive formula f(n) = 2(1 + n/2 - f(n/2)). Subtraction (Take 1-K): N % (K+1) === 0 → Lose. Nim: XOR of all piles = 0 → Lose (see separate Nim article). Valid Tic-Tac-Toe: Count X and O, check win states.
Key Insight
Q4: When should I use DP vs the formula? Always START with DP (the brute force). Build the table, show the pattern, THEN derive the formula. This demonstrates BOTH problem-solving approaches. Only use the formula directly if N is too large for DP (like 10⁹).
Key Insight
Q5: What if the allowed moves are NOT 1-K? Like allowed moves = [1, 3, 4]? Then the simple modulo pattern doesn't apply. You MUST use DP. But you can still optimize: find the period of the DP pattern (it often repeats) and compute N modulo that period.
Key Insight
Q6: What's the "choose/not-choose" pattern in game theory? At every position, you choose a move. If ANY move takes you to a losing position for the opponent, you WIN. If ALL moves lead to winning positions for the opponent, you LOSE. This choose/not-choose IS the game DP recurrence.
Key Insight
Q7: How do I handle the "misère" variant? Misère = player who takes the LAST loses (instead of wins). This changes the base cases but the recurrence is the same. Build the DP from scratch with the new winning condition — don't guess the pattern.
Key Insight
Q8: Any tips for the "reach 0" vs "take last wins" distinction? They're the SAME thing! If you need to reach 0, the player who reaches 0 wins = the player who takes the last stone. The game ends when no stones remain. Don't overthink this — same DP, same pattern.
📝 Key Takeaways
Golden Rule — A position is winning if a move to a losing position exists; losing if all moves go to winning positions. This is the ENGINE of all game DP.
Divisor Game (Leetcode 1025) — Even N → Alice wins. Odd N → Alice loses. The O(1) solution is return N % 2 === 0.
Subtraction Game (Take 1-K) — Losing position: N % (K+1) === 0. Memorize this pattern!
Always brute-force DP first — Build the table for N=0..20, find the pattern, THEN optimize. This impresses interviewers.
Maximum take determines the modulo — If you can take up to K, the magic number is K+1.
Many problems are isomorphic — "Game of Stairs" = "Subtraction Game" = "Take-Away Game". Same math, different story.
Arbitrary move sets need DP — The simple modulo only works for consecutive moves [1..K]. For [1,3,4], use DP or find periodicity.
Valid Tic-Tac-Toe — Use counting rules: X goes first, counts differ by at most 1, only one winner.
Practice makes permanent — Solve the 14 problems linked below. Each reinforces a different pattern. Your 🧠 will build pattern-matching muscle!
Note
🔮 What's Next? You've mastered divisor and elimination patterns! Head over to Nim & XOR Strategyto learn about Nim-sum and the XOR strategy that dominates competitive programming!
function divisorGame(N) { // dp[i] = true if the player at turn with number i can win const dp = new Array(N + 1).fill(false); // dp[1] = false (can't pick x where 0 < x < 1) // dp[2] = true (pick x=1, opponent gets 1 — they lose) for (let i = 2; i <= N; i++) { for (let x = 1; x < i; x++) { if (i % x === 0) { // If we can move to a LOSING position → we WIN if (!dp[i - x]) { dp[i] = true; break; // Found a winning move! } } } } return dp[N];}
function divisorGameOptimal(N) { // 🚀 ONE LINE: Even N → Alice wins, Odd N → Alice loses return N % 2 === 0;}
function lastRemaining(n) { let arr = Array.from({ length: n }, (_, i) => i + 1); let leftToRight = true; while (arr.length > 1) { const next = []; if (leftToRight) { // Left to right → keep 2nd, 4th, 6th... for (let i = 1; i < arr.length; i += 2) { next.push(arr[i]); } } else { // Right to left → keep 2nd-to-last, 4th-to-last... for (let i = arr.length - 2; i >= 0; i -= 2) { next.push(arr[i]); // push reverses order — that's fine } next.reverse(); } arr = next; leftToRight = !leftToRight; } return arr[0];}
// f(n) = last number with n elements, starting left→right// g(n) = last number with n elements, starting right→left// After one L→R pass, we have: 2 × [1, 2, ..., n/2]// But direction flips, so we use g(n/2) for the inner problemf(n) = 2 × g(floor(n/2))// Similarly for R→L:g(n) = 2 × f(floor(n/2)) - 1 (adjusted for right-start offset)// Combine them → elegant O(log n) recursion!function lastRemaining(n) { if (n === 1) return 1; // After first L→R pass: 2, 4, 6, ..., 2*(n/2) // Now solve the same problem on n/2, but starting R→L return 2 * (1 + Math.floor(n / 2) - lastRemaining(Math.floor(n / 2)));}
function canWinNim(N) { // dp[i] = can the current player win with i stones? const dp = new Array(N + 1).fill(false); // Base case: 0 stones → no move → lose dp[0] = false; for (let i = 1; i <= N; i++) { for (const take of [1, 2, 3]) { if (i >= take && !dp[i - take]) { dp[i] = true; // Move to opponent's losing position break; } } } return dp[N];}
function canWinNimOptimal(N) { // If N is a multiple of 4 → first player loses return N % 4 !== 0;}
// Generalized: can take 1 to K stonesfunction canWinGeneral(N, K) { return N % (K + 1) !== 0;}
function validTicTacToe(board) { const count = { X: 0, O: 0 }; for (const row of board) { for (const c of row) { if (c !== ' ') count[c]++; } } // X goes first → X count is either equal to O or one more if (count['X'] !== count['O'] && count['X'] !== count['O'] + 1) { return false; } const win = (player) => { // Check rows, cols, diagonals for (let i = 0; i < 3; i++) { if (board[i][0] === player && board[i][1] === player && board[i][2] === player) return true; if (board[0][i] === player && board[1][i] === player && board[2][i] === player) return true; } if (board[0][0] === player && board[1][1] === player && board[2][2] === player) return true; if (board[0][2] === player && board[1][1] === player && board[2][0] === player) return true; return false; }; const xWin = win('X'), oWin = win('O'); // Both can't win simultaneously if (xWin && oWin) return false; // If X wins, X must have one more move than O if (xWin && count['X'] !== count['O'] + 1) return false; // If O wins, counts must be equal if (oWin && count['X'] !== count['O']) return false; return true;}