Watch 3 video solutions for Game of Nim, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by Programming Live with Larry has 572 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice and Bob take turns playing a game with Alice starting first.
In this game, there are n piles of stones. On each player's turn, the player should remove any positive number of stones from a non-empty pile of his or her choice. The first player who cannot make a move loses, and the other player wins.
Given an integer array piles, where piles[i] is the number of stones in the ith pile, return true if Alice wins, or false if Bob wins.
Both Alice and Bob play optimally.
Example 1:
Input: piles = [1] Output: true Explanation: There is only one possible scenario: - On the first turn, Alice removes one stone from the first pile. piles = [0]. - On the second turn, there are no stones left for Bob to remove. Alice wins.
Example 2:
Input: piles = [1,1] Output: false Explanation: It can be proven that Bob will always win. One possible scenario is: - On the first turn, Alice removes one stone from the first pile. piles = [0,1]. - On the second turn, Bob removes one stone from the second pile. piles = [0,0]. - On the third turn, there are no stones left for Alice to remove. Bob wins.
Example 3:
Input: piles = [1,2,3] Output: false Explanation: It can be proven that Bob will always win. One possible scenario is: - On the first turn, Alice removes three stones from the third pile. piles = [1,2,0]. - On the second turn, Bob removes one stone from the second pile. piles = [1,1,0]. - On the third turn, Alice removes one stone from the first pile. piles = [0,1,0]. - On the fourth turn, Bob removes one stone from the second pile. piles = [0,0,0]. - On the fifth turn, there are no stones left for Alice to remove. Bob wins.
Constraints:
n == piles.length1 <= n <= 71 <= piles[i] <= 7
Follow-up: Could you find a linear time solution? Although the linear time solution may be beyond the scope of an interview, it could be interesting to know.
Problem Overview: You are given an array where each element represents the number of stones in a pile. Two players take turns removing any positive number of stones from a single pile. The player who cannot make a move loses. Your task is to determine whether the first player wins assuming both players play optimally.
Approach 1: Brute Force Game Simulation (Exponential Time, Exponential Space)
Model the game as a full decision tree. For every pile, try removing 1..k stones and recursively evaluate the resulting state. If any move leads to a losing position for the opponent, the current state is winning. This approach directly simulates optimal play but quickly explodes in complexity because each state branches into multiple new states. Time complexity is exponential in the total number of stones, and space is also exponential due to recursion and state storage. This approach demonstrates the fundamentals of game theory but is not practical for large inputs.
Approach 2: Dynamic Programming with Memoization (Exponential States)
Instead of recomputing the same states, cache previously evaluated pile configurations. Represent the state using a sorted tuple of pile sizes and store whether the position is winning or losing. Each recursive call iterates through every pile and every possible removal count. Memoization eliminates duplicate work, but the number of unique configurations is still extremely large. Time complexity remains exponential in the worst case, with exponential memory for cached states. This approach shows how dynamic programming can reduce repeated computation in combinatorial games.
Approach 3: Nim-Sum XOR Rule (O(n) Time, O(1) Space)
The optimal solution relies on a classic result from the mathematical theory of Nim. Compute the XOR of all pile sizes, often called the Nim-sum. If the XOR result is zero, the current player is in a losing position assuming optimal play. If it is non-zero, the current player can always make a move that forces the opponent into a zero XOR state. Implementation is straightforward: iterate through the array, compute the cumulative XOR using bit manipulation, and check whether the result is zero.
Recommended for interviews: Interviewers expect the Nim-sum insight. A brute force explanation shows you understand game state exploration, but recognizing the XOR property demonstrates strong algorithmic reasoning and familiarity with classic game theory problems. The optimal implementation runs in O(n) time and constant space.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Game Simulation | Exponential | Exponential | Useful for understanding basic game state recursion and optimal play logic. |
| Dynamic Programming with Memoization | Exponential (reduced by caching) | Exponential | When exploring theoretical game states and avoiding repeated calculations. |
| Nim-Sum XOR Rule | O(n) | O(1) | Best approach for production code and coding interviews. |