LeetCode 1908 - Game of Nim

This problem is the classic mathematical game known as Nim. We are given an array piles, where each element represents the number of stones in a pile. Two players, Alice and Bob, take turns removing stones.

leetcodemediumarraymathdynamic-programmingbit-manipulationbrainteasergame-theory

LeetCode Problem 1908

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Bit Manipulation, Brainteaser, Game Theory

Solution

Problem Understanding

This problem is the classic mathematical game known as Nim. We are given an array piles, where each element represents the number of stones in a pile. Two players, Alice and Bob, take turns removing stones. On each turn, a player may choose any non-empty pile and remove any positive number of stones from it.

Alice always moves first. The player who cannot make a move loses the game.

The task is to determine whether Alice wins if both players play optimally. In other words, we are not simulating arbitrary gameplay. We must assume both players always choose the move that maximizes their chance of winning.

The constraints are extremely small:

  • There are at most 7 piles
  • Each pile contains at most 7 stones

These limits are small enough that a brute-force recursive game simulation is feasible. However, the follow-up asks for a linear time solution, which hints that there is a deeper mathematical property of the game.

The key observation is that this is exactly the standard Nim game. Nim has a well-known optimal strategy based on the XOR of all pile sizes.

Some important edge cases immediately stand out:

  • A single pile always means the first player wins, because Alice can remove all stones immediately.
  • If all piles XOR to zero, the first player loses under optimal play.
  • Multiple identical piles can create balanced states that are losing positions.
  • The problem guarantees every pile has at least one stone, so we never need to handle negative values or empty input arrays.

Approaches

Brute Force Approach

The brute-force solution models the game recursively.

For every game state, we try every possible move:

  • Choose a non-empty pile
  • Remove between 1 and pile_size stones
  • Recursively evaluate whether the opponent can win from the resulting state

A position is winning if there exists at least one move that forces the opponent into a losing position.

This approach is correct because it explicitly explores the complete game tree and follows the formal definition of optimal play in combinatorial games.

However, the number of states grows exponentially as the number of piles and stones increase. Even though the constraints here are small enough to allow memoization, the approach is still far slower and more complicated than necessary.

Optimal Approach

The optimal solution uses the mathematical property of Nim.

The central theorem of Nim states:

  • If the XOR of all pile sizes is 0, the current player loses with optimal play.
  • Otherwise, the current player wins with optimal play.

This XOR value is commonly called the "nim-sum".

The reason this works is rooted in game theory. A non-zero XOR state always has at least one move that transforms the game into a zero XOR state. Conversely, every move from a zero XOR state necessarily produces a non-zero XOR state.

Therefore:

  • Alice wins if the XOR of all piles is non-zero.
  • Bob wins if the XOR is zero.

This reduces the problem to a simple linear scan through the array.

Approach Time Complexity Space Complexity Notes
Brute Force O(state space) O(state space) Recursively explores all possible game states
Optimal O(n) O(1) Uses Nim XOR theorem

Algorithm Walkthrough

  1. Initialize a variable called xor_sum to 0.

This variable will store the cumulative XOR of all pile sizes. 2. Iterate through every pile in the array.

For each pile:

  • Compute xor_sum ^= pile

XOR has useful cancellation properties:

  • a ^ a = 0
  • a ^ 0 = a

The final XOR value summarizes the entire game state. 3. After processing all piles, check whether xor_sum equals 0.

  • If it is 0, return False because Alice loses under optimal play.
  • Otherwise, return True because Alice can force a win.

Why it works

The correctness follows directly from the Sprague-Grundy theory for Nim.

A zero XOR state is a losing position because every possible move changes the XOR to a non-zero value, giving the opponent a winning position.

A non-zero XOR state is a winning position because there always exists a move that changes the XOR to zero, forcing the opponent into a losing state.

Since both players play optimally, the first player wins exactly when the initial XOR is non-zero.

Python Solution

from typing import List

class Solution:
    def nimGame(self, piles: List[int]) -> bool:
        xor_sum = 0

        for pile in piles:
            xor_sum ^= pile

        return xor_sum != 0

The implementation is extremely compact because the mathematical insight eliminates the need for recursion or dynamic programming.

The variable xor_sum starts at zero. As we iterate through the array, we continuously XOR each pile size into the running total.

At the end:

  • xor_sum == 0 means the position is losing for the current player
  • xor_sum != 0 means the position is winning for the current player

Since Alice moves first, the function simply returns whether the final XOR is non-zero.

Go Solution

func nimGame(piles []int) bool {
    xorSum := 0

    for _, pile := range piles {
        xorSum ^= pile
    }

    return xorSum != 0
}

The Go implementation follows exactly the same logic as the Python version.

Go uses the ^ operator for bitwise XOR just like Python. Since the constraints are tiny, integer overflow is not a concern. The solution uses constant extra space and only iterates through the slice once.

Worked Examples

Example 1

Input:

piles = [1]

Step-by-step XOR computation:

Step Pile xor_sum
Initial - 0
Process pile 1 1 0 ^ 1 = 1

Final result:

xor_sum = 1

Since the XOR is non-zero, Alice wins.

Output:

true

Example 2

Input:

piles = [1,1]

Step-by-step XOR computation:

Step Pile xor_sum
Initial - 0
Process first pile 1 0 ^ 1 = 1
Process second pile 1 1 ^ 1 = 0

Final result:

xor_sum = 0

Since the XOR is zero, Bob wins.

Output:

false

Example 3

Input:

piles = [1,2,3]

Step-by-step XOR computation:

Step Pile xor_sum
Initial - 0
Process first pile 1 0 ^ 1 = 1
Process second pile 2 1 ^ 2 = 3
Process third pile 3 3 ^ 3 = 0

Final result:

xor_sum = 0

Since the XOR is zero, Bob wins.

Output:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through the piles array exactly once
Space O(1) Only one integer variable is used

The algorithm is optimal because every pile must be examined at least once to compute the XOR. No auxiliary data structures are required.

Test Cases

sol = Solution()

assert sol.nimGame([1]) == True          # Single pile, Alice removes all stones
assert sol.nimGame([1, 1]) == False     # XOR becomes zero
assert sol.nimGame([1, 2, 3]) == False  # Classic losing Nim state
assert sol.nimGame([1, 2, 4]) == True   # Non-zero XOR
assert sol.nimGame([7]) == True         # Maximum single pile
assert sol.nimGame([2, 2]) == False     # Equal piles cancel out
assert sol.nimGame([3, 3, 3]) == True   # XOR is non-zero
assert sol.nimGame([4, 4, 4, 4]) == False  # Even duplicates cancel completely
assert sol.nimGame([1, 1, 1]) == True   # Odd duplicates leave non-zero XOR
assert sol.nimGame([7, 7, 7, 7, 7]) == True  # Large repeated values
assert sol.nimGame([1, 3, 5, 7]) == False    # XOR evaluates to zero
assert sol.nimGame([2, 5, 6]) == True        # Random winning state
Test Why
[1] Smallest valid input
[1,1] Simple losing state
[1,2,3] Common Nim example with zero XOR
[1,2,4] Basic winning configuration
[7] Maximum pile value
[2,2] Duplicate cancellation
[3,3,3] Odd number of duplicates
[4,4,4,4] Even duplicate cancellation
[1,1,1] Non-zero XOR from repeated values
[7,7,7,7,7] Stress repeated maximum values
[1,3,5,7] Larger zero XOR state
[2,5,6] Random non-zero XOR state

Edge Cases

Single Pile

When there is only one pile, Alice can always remove all stones immediately and win. A naive implementation might overcomplicate this case with recursion, but the XOR rule handles it naturally. The XOR of a single positive number is always non-zero, so the algorithm correctly returns True.

All Piles Cancel Out

Inputs like [1,1] or [4,4,4,4] produce an XOR of zero. These are losing states for the first player. This can feel unintuitive because there are still many stones available, but mathematically every move breaks the balance and gives the opponent a winning response.

The implementation handles this correctly by directly checking whether the final XOR equals zero.

Repeated Values with Odd Count

Cases like [3,3,3] are important because duplicate values do not always cancel completely. Two 3s cancel out, but the remaining 3 leaves a non-zero XOR.

A buggy implementation might incorrectly assume repeated values always form losing states. The XOR computation naturally distinguishes between even and odd counts, so the solution remains correct.