Skip to main content

Nim Game: Complete Journey

Problem: Given n stones, two players take turns removing 1-3 stones. The player who takes the last stone wins. Both play optimally. Can the first player win?

Problem Statement​

LeetCode 292 - Nim Game

You are playing a Nim Game with your friend:

  • Initially, there are n stones in a pile
  • You and your friend take turns removing stones
  • On each turn, you can remove 1, 2, or 3 stones
  • The one who removes the last stone wins
  • Both players play optimally

Given n, return true if you can win the game assuming both players play optimally, otherwise return false.

Example 1:

Input: n = 4
Output: false
Explanation:
- You take 1 → 3 left → opponent takes 3 → opponent wins
- You take 2 → 2 left → opponent takes 2 → opponent wins
- You take 3 → 1 left → opponent takes 1 → opponent wins
All moves lead to opponent winning!

Example 2:

Input: n = 1
Output: true
Explanation: You take 1 stone and win immediately.

Common Mistakes & Solutions​

This problem is excellent for learning game theory DP because it exposes three critical mistakes beginners make.

❌ Mistake 1: Incorrect Base Case Logic​

// WRONG!
if (number == 0 && whoisme == true) {
    return true;  // "If it's my turn and 0 stones left, I won"
}

Why it's wrong: If it's your turn and there are 0 stones left, you've already lost! The opponent took the last stone on their previous turn. The game is over, and you're staring at an empty pile.

Think about it:

  • The person who takes the last stone wins
  • If n = 0 on your turn, the last stone was taken by your opponent
  • You have no moves available → you lose

✅ Correct Base Case:

// If no stones left, current player has already lost
if (n == 0) {
    return false;
}

// Alternative: More explicit base cases
if (n <= 3 && isMyTurn) {
    return true;   // I can take all remaining stones and win
}
if (n <= 3 && !isMyTurn) {
    return false;  // Opponent can take all remaining stones and win
}

❌ Mistake 2: Not Subtracting Stones from State​

// WRONG!
a = func(1, !whoisme)  // Should be: func(number - 1, !whoisme)
b = func(2, !whoisme)  // Should be: func(number - 2, !whoisme)
c = func(3, !whoisme)  // Should be: func(number - 3, !whoisme)

Why it's wrong: You're trying to explore what happens when you REMOVE stones. The parameters to the recursive call should represent the NEW STATE after your move.

Think about it:

  • If there are 10 stones and you take 3, how many are left? 7!
  • The next state should have n - 3 stones
  • You're calling func(3, ...) which means "3 stones left", not "take 3 stones"

✅ Correct Recursion:

// Try all possible moves
if (n >= 1) a = canWinNim(n - 1, !isMyTurn);  // Take 1 → (n-1) left
if (n >= 2) b = canWinNim(n - 2, !isMyTurn);  // Take 2 → (n-2) left
if (n >= 3) c = canWinNim(n - 3, !isMyTurn);  // Take 3 → (n-3) left

Pro tip: Always validate moves before making them (if (n >= 1), if (n >= 2), etc.) to avoid invalid states.

❌ Mistake 3: Wrong Return Logic (The Most Subtle!)​

// WRONG!
return a || b || c;  // "I win if opponent wins from any move??"

Why it's wrong: This is the most confusing part of game theory DP. Let's break it down:

What do a, b, c represent?

  • a = canWinNim(n-1, false) means "Can opponent win with n-1 stones?"
  • b = canWinNim(n-2, false) means "Can opponent win with n-2 stones?"
  • c = canWinNim(n-3, false) means "Can opponent win with n-3 stones?"

So return a || b || c means:

  • "I win if opponent wins from at least one of my moves"
  • That makes NO sense! If opponent wins, YOU lose!

✅ Correct Return Logic:

// On my turn: I win if ANY move puts opponent in a losing position
return !a || !b || !c;  // At least one move makes opponent lose

// Equivalently (using De Morgan's Law):
return !(a && b && c);  // I lose only if ALL moves lead to opponent winning

Think about it:

  • !a means "opponent CANNOT win after I take 1 stone"
  • !b means "opponent CANNOT win after I take 2 stones"
  • !c means "opponent CANNOT win after I take 3 stones"
  • !a || !b || !c means "There exists at least one move that makes opponent lose"
  • If opponent loses, you WIN! ✅

Mental Model:

Winning = "I have at least ONE move that puts opponent in a losing position"
Losing  = "ALL my moves put opponent in a winning position"

Step-by-Step Solution Development​

Step 1: Unoptimized Recursion​

public boolean canWinNim(int n, boolean isMyTurn) {
    // Base case: no stones left means current player loses
    if (n == 0) {
        return false;
    }

    // Base case: can take all remaining stones
    if (n <= 3 && isMyTurn) {
        return true;   // I win by taking all stones
    }
    if (n <= 3 && !isMyTurn) {
        return false;  // Opponent wins by taking all stones
    }

    if (isMyTurn) {
        // Try all possible moves (take 1, 2, or 3 stones)
        boolean take1 = canWinNim(n - 1, false);  // After I take 1
        boolean take2 = canWinNim(n - 2, false);  // After I take 2
        boolean take3 = canWinNim(n - 3, false);  // After I take 3

        // I win if ANY move puts opponent in losing position
        return !take1 || !take2 || !take3;
    } else {
        // Opponent's turn
        boolean take1 = canWinNim(n - 1, true);
        boolean take2 = canWinNim(n - 2, true);
        boolean take3 = canWinNim(n - 3, true);

        // Opponent will make best move for them (worst for me)
        // I lose if they have ANY winning move
        return !(take1 || take2 || take3);
    }
}

Complexity:

  • Time: O(3^n) - exponential! Each call branches into 3 more calls
  • Space: O(n) - recursion depth

Call this with: canWinNim(n, true) (you go first)

Step 2: Add Memoization (Top-Down DP)​

public boolean canWinNim(int n) {
    // Cache: [n][turn] where turn: 0 = my turn, 1 = opponent's turn
    Boolean[][] memo = new Boolean[n + 1][2];
    return canWin(n, true, memo);
}

private boolean canWin(int n, boolean isMyTurn, Boolean[][] memo) {
    // Base cases
    if (n == 0) return false;
    if (n <= 3 && isMyTurn) return true;
    if (n <= 3 && !isMyTurn) return false;

    // Check cache
    int turn = isMyTurn ? 0 : 1;
    if (memo[n][turn] != null) {
        return memo[n][turn];  // Already computed!
    }

    boolean result;
    if (isMyTurn) {
        boolean take1 = canWin(n - 1, false, memo);
        boolean take2 = canWin(n - 2, false, memo);
        boolean take3 = canWin(n - 3, false, memo);
        result = !take1 || !take2 || !take3;
    } else {
        boolean take1 = canWin(n - 1, true, memo);
        boolean take2 = canWin(n - 2, true, memo);
        boolean take3 = canWin(n - 3, true, memo);
        result = !(take1 || take2 || take3);
    }

    memo[n][turn] = result;  // Cache result
    return result;
}

Complexity:

  • Time: O(n) - compute each state only once
  • Space: O(n) - cache size

Huge improvement: Exponential → Linear time!

Step 3: Bottom-Up DP (Iterative)​

public boolean canWinNim(int n) {
    if (n <= 3) return true;

    // dp[i][0] = can I win with i stones on my turn
    // dp[i][1] = can I win with i stones on opponent's turn
    boolean[][] dp = new boolean[n + 1][2];

    // Base cases
    for (int i = 1; i <= 3 && i <= n; i++) {
        dp[i][0] = true;   // My turn: I can take all stones and win
        dp[i][1] = false;  // Opponent's turn: they take all and I lose
    }

    // Fill table bottom-up
    for (int i = 4; i <= n; i++) {
        // My turn: I win if ANY move puts opponent in losing position
        dp[i][0] = !dp[i-1][1] || !dp[i-2][1] || !dp[i-3][1];

        // Opponent's turn: I win only if ALL their moves lead to my winning
        dp[i][1] = dp[i-1][0] && dp[i-2][0] && dp[i-3][0];
    }

    return dp[n][0];
}

Complexity:

  • Time: O(n)
  • Space: O(n)

No recursion overhead: Iterative is slightly faster in practice.

Step 4: Mathematical Insight ⚡ (O(1) Solution!)​

After building the DP table, you'll notice a pattern:

n=1:  true   (take 1, win)
n=2:  true   (take 2, win)
n=3:  true   (take 3, win)
n=4:  false  (opponent wins)
n=5:  true   (take 1 → leave 4 for opponent)
n=6:  true   (take 2 → leave 4 for opponent)
n=7:  true   (take 3 → leave 4 for opponent)
n=8:  false  (opponent wins)
n=9:  true
...

Pattern: You lose if and only if n % 4 == 0!

Why?

  • If n % 4 == 0: Whatever you take (1, 2, or 3), opponent can take 4 - your_move to maintain the pattern
    • You take 1 → they take 3 → back to multiple of 4
    • You take 2 → they take 2 → back to multiple of 4
    • You take 3 → they take 1 → back to multiple of 4
  • If n % 4 != 0: You can always make it divisible by 4 for your opponent
    • n % 4 == 1 → take 1 → leave multiple of 4
    • n % 4 == 2 → take 2 → leave multiple of 4
    • n % 4 == 3 → take 3 → leave multiple of 4

✅ Final O(1) Solution:

public boolean canWinNim(int n) {
    return n % 4 != 0;
}

Complexity:

  • Time: O(1) - single modulo operation!
  • Space: O(1) - no extra space

Mind-blowing optimization: From exponential to constant time!

Always draw the game tree for small inputs to understand the pattern.

Example: n = 4​

                    n=4 (MY turn)
                    /      |      \
              take 1   take 2   take 3
                /         |         \
            n=3(OPP)   n=2(OPP)   n=1(OPP)
            opp takes  opp takes  opp takes
            all 3      all 2      1 stone
            OPP WINS   OPP WINS   OPP WINS
               ✗          ✗          ✗

All my moves → opponent wins → I LOSE → return false ✅

Example: n = 5​

                    n=5 (MY turn)
                    /      |      \
              take 1   take 2   take 3
                /         |         \
            n=4(OPP)   n=3(OPP)   n=2(OPP)
            opp loses  opp takes  opp takes
            (from      all 3      all 2
            above)     OPP WINS   OPP WINS
            I WIN!        ✗          ✗
               ✓

At least ONE move → opponent loses → I WIN → return true ✅

Key Takeaways​

🎯 Perspective Switching​

  • Recursive calls return result from opponent's perspective
  • You must negate to get your perspective
  • !oppWins means "opponent doesn't win" = "you win"

🎯 Base Cases Matter​

  • n == 0: Current player has lost (opponent took last stone)
  • n <= 3 && myTurn: I can take all and win
  • Think carefully about who wins in terminal states

🎯 State Transitions​

  • Subtract stones you're taking: n - move
  • Flip turn: !isMyTurn
  • Always validate move is legal before making it

🎯 Return Logic Pattern​

// I win if ANY move makes opponent lose
return !move1_opp_wins || !move2_opp_wins || !move3_opp_wins;

// Equivalently
return !(move1_opp_wins && move2_opp_wins && move3_opp_wins);

🎯 Optimization Progression​

  1. Unoptimized Recursion: Understand the logic (O(3^n))
  2. Memoization: Cache results (O(n))
  3. Bottom-Up: Remove recursion overhead (O(n))
  4. Mathematical Pattern: Look for shortcuts (O(1))

Practice Challenge​

Try implementing this yourself from scratch:

  1. Draw the decision tree for n=1,2,3,4,5,6
  2. Write the unoptimized recursive solution
  3. Add memoization
  4. Convert to bottom-up DP
  5. Spot the pattern and write O(1) solution

Debugging tip: If your solution is wrong, print the decision tree for small n and trace through your logic step by step.

Once you master Nim Game, try these variants:

  1. Stone Game (LC 877) - Pick from ends of array instead of taking arbitrary amounts
  2. Stone Game II (LC 1140) - Variable number of stones you can take (controlled by M)
  3. Stone Game III (LC 1406) - Can take 1, 2, or 3 stones from beginning of array
  4. Can I Win (LC 464) - Similar but with number selection and target sum

Remember: Game theory DP is all about perspective. You're optimizing for yourself while assuming your opponent does the same. The key insight is that return !opponent_wins means YOU win! 🎯