LeetCode 292 - Nim Game

The problem describes a two-player game involving a single heap of stones. There are n stones initially on the table, and players alternate turns removing stones. On each turn, a player may remove either 1, 2, or 3 stones. The player who removes the final stone wins the game.

leetcodeeasymathbrainteasergame-theory

LeetCode Problem 292

Difficulty: 🟢 Easy
Topics: Math, Brainteaser, Game Theory

Solution

Problem Understanding

The problem describes a two-player game involving a single heap of stones. There are n stones initially on the table, and players alternate turns removing stones. On each turn, a player may remove either 1, 2, or 3 stones. The player who removes the final stone wins the game.

You always move first, and both players are assumed to play optimally. This means neither player will make random or greedy moves. Instead, each player will always choose the move that maximizes their own chance of winning.

The input is a single integer n, representing the number of stones in the heap. The output is a boolean value:

  • Return true if the first player can force a win.
  • Return false if the second player can force a win regardless of what the first player does.

The constraint is:

  • 1 <= n <= 2^31 - 1

This constraint is important because it tells us the input can be extremely large. Any solution that recursively explores all possibilities or builds a large dynamic programming table may become inefficient or even impossible for the upper bound.

Several edge cases are important immediately:

  • n = 1, the first player removes the only stone and wins.
  • n = 2 or n = 3, the first player can also win immediately.
  • n = 4 is the first losing state because every possible move leaves a winning position for the opponent.
  • Very large values such as 2^31 - 1 require constant time computation.

The key challenge is identifying the mathematical pattern that determines whether a position is winning or losing.

Approaches

Brute Force Approach

A straightforward approach is to recursively simulate every possible move. From a given number of stones n, the current player can remove 1, 2, or 3 stones and leave the opponent with n - 1, n - 2, or n - 3 stones.

The recursive logic works as follows:

  • A state is winning if at least one move leads to a losing state for the opponent.
  • A state is losing if every possible move leads to a winning state for the opponent.

For example:

  • n = 1, winning because you can take the last stone.
  • n = 2, winning because you can take both stones.
  • n = 3, winning because you can take all stones.
  • n = 4, losing because every move leaves 1, 2, or 3 stones, all of which are winning states.

This recursive process correctly models optimal play because each player always chooses the best available move.

However, naive recursion repeatedly recalculates the same states. Even with memoization, the solution still requires O(n) time and space, which is unnecessary for this problem. Since n can be extremely large, we should look for a mathematical shortcut.

Key Insight

The critical observation is that every multiple of 4 is a losing position.

We can see the pattern by analyzing small values:

n Result
1 Win
2 Win
3 Win
4 Lose
5 Win
6 Win
7 Win
8 Lose

Why does this happen?

If the number of stones is a multiple of 4:

  • Removing 1 leaves a multiple of 4 minus 1.
  • Removing 2 leaves a multiple of 4 minus 2.
  • Removing 3 leaves a multiple of 4 minus 3.

In every case, the opponent receives a non-multiple of 4.

Then the opponent can always respond by removing enough stones to bring the heap back to a multiple of 4.

For example:

  • If you remove 1, the opponent removes 3.
  • If you remove 2, the opponent removes 2.
  • If you remove 3, the opponent removes 1.

Together, each pair of turns removes exactly 4 stones.

Because of this invariant, the player who starts on a multiple of 4 eventually loses.

Therefore:

  • If n % 4 == 0, return false
  • Otherwise, return true

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n) naive recursion, O(n) with memoization O(n) Explores game states recursively
Optimal O(1) O(1) Uses the mathematical property of multiples of 4

Algorithm Walkthrough

Optimal Algorithm

  1. Receive the input integer n, representing the number of stones in the heap.
  2. Compute n % 4.

The modulo operation determines whether n is divisible by 4. 3. If n % 4 == 0, return False.

A multiple of 4 is always a losing position when both players play optimally. No matter what move the current player makes, the opponent can always restore the game to another multiple of 4. 4. Otherwise, return True.

If the number is not divisible by 4, the current player can remove 1, 2, or 3 stones to force the opponent into a multiple-of-4 position.

Why it works

The core invariant is that multiples of 4 are losing states. Every move removes between 1 and 3 stones, so from a multiple of 4, the next player always receives a non-multiple of 4. Conversely, from any non-multiple of 4, the current player can always move to a multiple of 4. Repeating this strategy guarantees victory for the player who first forces the opponent into a multiple-of-4 state.

Python Solution

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

The implementation is intentionally minimal because the entire game reduces to a mathematical observation.

The expression n % 4 computes the remainder after dividing by 4.

  • If the remainder is 0, then n is a multiple of 4 and the first player loses.
  • Otherwise, the first player can force a win by moving the game into a multiple-of-4 state.

The solution uses constant time and constant space, making it efficient even for the maximum allowed input size.

Go Solution

func canWinNim(n int) bool {
    return n%4 != 0
}

The Go implementation is nearly identical to the Python version because the logic is purely mathematical.

Go uses the % operator for modulo operations exactly like Python. Since the problem guarantees that n fits within the valid integer range, there are no overflow concerns in this calculation.

No additional memory allocations or data structures are required.

Worked Examples

Example 1

Input:

n = 4

Step-by-step evaluation:

Step Value
Compute 4 % 4 0
Is remainder 0? Yes
Return False

Interpretation:

No matter whether the first player removes 1, 2, or 3 stones, the opponent can always take the remaining stones and win.

Example 2

Input:

n = 1

Step-by-step evaluation:

Step Value
Compute 1 % 4 1
Is remainder 0? No
Return True

Interpretation:

The first player removes the only stone and wins immediately.

Example 3

Input:

n = 2

Step-by-step evaluation:

Step Value
Compute 2 % 4 2
Is remainder 0? No
Return True

Interpretation:

The first player removes both stones and wins immediately.

Additional Example

Input:

n = 8

Step-by-step evaluation:

Turn Stones Remaining Action
Start 8 Multiple of 4
Player 1 removes 1 7
Player 2 removes 3 4 Restore multiple of 4
Player 1 removes 2 2
Player 2 removes 2 0 Player 2 wins

This demonstrates the multiple-of-4 strategy in action.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only one modulo operation is performed
Space O(1) No extra memory is used

The algorithm performs a single arithmetic operation regardless of the size of n. There are no loops, recursion calls, or auxiliary data structures. This makes the solution optimal in both time and space complexity.

Test Cases

solution = Solution()

assert solution.canWinNim(1) == True   # Smallest input, immediate win
assert solution.canWinNim(2) == True   # Can take all stones
assert solution.canWinNim(3) == True   # Can take all stones
assert solution.canWinNim(4) == False  # First losing position

assert solution.canWinNim(5) == True   # Remove 1 to leave 4
assert solution.canWinNim(6) == True   # Remove 2 to leave 4
assert solution.canWinNim(7) == True   # Remove 3 to leave 4
assert solution.canWinNim(8) == False  # Multiple of 4

assert solution.canWinNim(12) == False # Larger multiple of 4
assert solution.canWinNim(15) == True  # Non-multiple of 4
assert solution.canWinNim(16) == False # Multiple of 4

assert solution.canWinNim(100) == False  # Large multiple of 4
assert solution.canWinNim(101) == True   # Large non-multiple of 4

assert solution.canWinNim(2**31 - 1) == True  # Maximum constraint value

Test Summary

Test Why
n = 1 Verifies smallest valid input
n = 2 Tests immediate winning state
n = 3 Tests another immediate winning state
n = 4 Verifies first losing configuration
n = 5 Confirms winning move to multiple of 4
n = 8 Confirms larger losing multiple of 4
n = 12 Tests repeated pattern
n = 100 Tests large multiple of 4
n = 101 Tests large non-multiple of 4
2^31 - 1 Verifies handling of maximum constraint

Edge Cases

One important edge case is when n = 1. A naive implementation might overcomplicate the logic with recursion or dynamic programming, but the optimal solution handles it naturally. Since 1 % 4 != 0, the algorithm correctly returns True.

Another critical edge case is any multiple of 4, such as n = 4, 8, or 100. These are the only losing states in the game. Many incorrect implementations fail because they do not recognize the repeating mathematical pattern and instead attempt to simulate moves inefficiently.

A third important edge case is the maximum allowed input, 2^31 - 1. Recursive or DP-based approaches may consume excessive memory or runtime for very large inputs. The mathematical solution avoids this entirely because it performs only a constant-time modulo operation regardless of input size.

A subtle edge case involves ensuring the modulo logic is applied correctly. Some incorrect solutions mistakenly use conditions like n <= 4 or attempt special handling for small numbers only. The repeating cycle means the rule applies uniformly to all positive integers, which is why the compact modulo solution is both correct and complete.