Interview Problem Explained: Nim Game (LeetCode 292, Recursion & Memoization)

Nim Game: Problem Statement

Two players take turns removing stones from a pile. The game starts with k stones, and each player can remove 1 to 3 stones per turn. The player who takes the last stone wins. Player A starts first. Determine if Player A can force a win, assuming both play optimally.

For example, when k = 5:

• If A removes 1 stone (leaving 4), B is forced into a losing position.

• If A removes 2 or 3 stones, B can take all remaining stones and win.

→ Thus, A’s optimal move is to take 1 stone, ensuring a win no matter what B chooses next.

Problem Requirements

1. Input: Integer k (1 ≤ k ≤ 2³¹ − 1).

2. Output: Return True if A can win, False otherwise.

Tip: This is Leetcode Problem 292.

Codetree enhances LeetCode’s concise descriptions with detailed explanations and examples for deeper understanding.

Step 1. Naive Approach

Idea

This is a classic naive simulation approach.

We want to determine:

“Can A win when there are x stones left?”

To do that, A considers every move (taking 1 to 3 stones), and checks whether—no matter how B responds—A can still win. This recursive process explores all possible game paths.

Logic Breakdown

1. Define a recursive function solve(x) that returns True if A can win with x stones, otherwise False.

2. Base Case: If x <= 6, we hardcode the result:

   • If x == 4 → A must lose → return False

   • Else → return True

3. For each of A’s moves (i = 1 to 3), simulate B’s response (j = 1 to 3)

4. If for any move i, A can guarantee a win regardless of B’s response, return True

Code Implementation

def solve(x):
    """
    :param x: int
    :return: bool
    """
    # Base case: only x == 4 is a losing position
    if x <= 6:
        return x != 4

    judge = False

    for i in range(1, 4):
        if all(solve(x - i - j) for j in range(1, 4)):
            judge = True
            break

    return judge

Time and Space Complexity

• For each state, there are 3 possible moves for A, and for each, 3 responses by B → up to 9 recursive calls per state.

• The recursion depth decreases by at least 2 per turn, so depth ≈ k / 2

• Worst-case complexity: O(3^k), which is exponential

→ Time Limit Exceeded for k ≤ 231 - 1

Space complexity is O(k) due to recursion stack.

Step 2. Memoization

Idea

The naive solution recalculates the same states repeatedly. For example, solve(10) may be computed many times while solving solve(16).

To fix this inefficiency, we apply memoization—a classic dynamic programming technique—by storing the results of previously computed states.

Logic Breakdown

1. Use a dictionary memo to cache solve(x) results

2. If x is not in memo, compute it and store it

3. Return the stored result if already computed

Code with Memoization

memo = {}

def solve(x):
    """
    :param x: int
    :return: bool
    """
    if x <= 6:
        return x != 4

    if x not in memo:
        memo[x] = False
        for i in range(1, 4):
            if all(solve(x - i - j) for j in range(1, 4)):
                memo[x] = True
                break

    return memo[x]

Time and Space Complexity

• Time: O(k) — each state is computed only once

• Space: O(k) — due to memo dictionary and recursion stack

Still inefficient for large k due to Python recursion limits.

Step 3. Discovering the Pattern

Idea

In Step 1 and 2, we focused on computing the result for each k using recursion or memoization. However, given that k can be as large as a billion, calculating the answer for every possible k is computationally infeasible and would lead to timeouts.

So let’s simulate the outcomes for smaller values. Try listing whether A wins (1) or loses (0) for k ≤ 20. Here's what the pattern looks like:

1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0

See the pattern?

• When k is a multiple of 4, the result is always 0 (A loses).

• Otherwise, the result is 1 (A wins).

Let’s break down why A must always lose when k is a multiple of 4:

• No matter what number of stones A picks (a from 1 to 3), B can always respond with 4 - a.

• Since both a and 4 - a are within the allowed range (1 to 3), this strategy is always possible.

• As a result, the total number of stones removed per round is always 4, and the game state returns to a multiple of 4 after each round.

• If the game starts at a multiple of 4, B will always be the one to take the last stone—A cannot win regardless of strategy.

Now, what if k is not a multiple of 4? In this case, a guaranteed winning strategy always exists for A.

• A can start by removing k % 4 stones, leaving a multiple of 4 for B.

• No matter what B picks next (b from 1 to 3), A can then respond with 4 - b to return the state back to a multiple of 4.

• By repeating this strategy, A can force B into a losing position every time and guarantee that A takes the final stone.

So with the right first move, A can control the game flow and reduce the remaining stones by 4 each round—ensuring victory.

Logic Breakdown

Let’s structure this pattern insight into a concise solution:

1. We define a function solve(x) that determines whether Player A can win if there are x stones remaining.

2. From earlier exploration, we discovered a repeating pattern:

   • If x is a multiple of 4, Player A will always lose.

   • If x is not a multiple of 4, Player A will always win.

3. Therefore, if x % 4 != 0, A can guarantee a win, and solve(x) should return True. Otherwise, if x % 4 == 0, A has no winning strategy and solve(x) should return False.

def solve(x):
    """
    :param x: int
    :return: bool
    """
    return x % 4 != 0

Time & Space Complexity Analysis

This observation allows us to derive a constant-time expression.

Thus, the time complexity is O(1), and there is no additional memory usage — space complexity is also O(1).

Frequently Asked Questions

Q. In an interview, should I emphasize memoization or the mathematical pattern?

It's best to walk through the entire progression step by step.

Start by discussing the naive approach, then introduce memoization to improve efficiency, and finally explain how you identified a pattern through experimentation and generalized it into a constant-time solution.

Q. What if the problem didn’t have a clear pattern like this?

In that case, this kind of optimization wouldn't be possible. This particular problem has a simple and repeating structure, which makes an O(1) solution viable. But more complex problems typically require a different approach.

How to Prepare for Interviews with the Nim Game Problem

Nim Game is a great interview prep question that lets you experience a full thought process: from recursive brute-force, to memoization, and finally to mathematical generalization. It’s a classic example of how a simple game can sharpen algorithmic and pattern-recognition skills.

You’ll strengthen the following skills:

• Understanding and constructing recursive function flows

• Applying memoization to remove redundant computations

• Recognizing and generalizing mathematical patterns from small examples

Similar Problems to Practice

• Divisor Game

• Nth Digit

• Shell Game

These problems also encourage you to spot mathematical patterns and generalize rules — ideal for building intuition around algorithm design.

How to Review After Solving This Problem

1. Summarize the logic progression.

   • Go over the key reasoning and complexity shifts from Naive → Memoization → Math-based solution.

   • Use sketches or mental models to map the transitions clearly.

2. Compare time complexity experimentally.

   • Try running different versions of your solution (recursive, memoized, and final version) to compare performance at increasing values of k.

3. Try variation problems.

   • What if you could take 1 to 5 stones at a time instead of 1 to 3?

   • What if there were multiple piles of stones instead of one?