Skip to main content
Talentd

Game of Nim - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathDynamic ProgrammingBit Manipulation7 min read
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 7
  • 1 <= 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.

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Game SimulationExponentialExponentialUseful for understanding basic game state recursion and optimal play logic.
Dynamic Programming with MemoizationExponential (reduced by caching)ExponentialWhen exploring theoretical game states and avoiding repeated calculations.
Nim-Sum XOR RuleO(n)O(1)Best approach for production code and coding interviews.

Video Solution

1908. Game of Nim - Week 5/5 Leetcode January Challenge • Programming Live with Larry • 579 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Game of Nim easy or hard?
Game of Nim is typically rated Medium because the optimal solution requires recognizing the XOR-based Nim-sum rule from game theory. The implementation itself is simple, but identifying the mathematical insight is the key challenge.
Game of Nim Python/Java solution
The implementation in Python, Java, C++, Go, or TypeScript simply iterates through the pile array and XORs each value with a running variable. After the loop, return true if the XOR result is not zero, otherwise return false.
How to solve Game of Nim in O(n)?
Iterate through the piles array and compute the XOR of all values. This cumulative XOR is called the Nim-sum. If the final XOR equals zero, the first player loses under optimal play; otherwise the first player wins. The algorithm performs a single pass over the array.
What is the best approach for Game of Nim?
The optimal approach uses the Nim-sum rule. Compute the XOR of all pile sizes and check the result. If the XOR is non-zero, the first player has a winning move; if it is zero, the first player loses with optimal play. This solution runs in O(n) time and O(1) space.
Is Game of Nim asked at Google/Amazon/Meta?
Game of Nim is a classic game theory interview problem and variations appear in interviews at companies like Google, Amazon, and Meta. Interviewers often use it to test understanding of XOR properties, mathematical reasoning, and optimal play strategies.
What data structure is used in Game of Nim?
The solution primarily uses an array to represent piles and bitwise XOR operations to compute the Nim-sum. No additional data structures are required for the optimal solution, which keeps the space complexity constant.
What is the time complexity of Game of Nim?
Using the optimal XOR-based strategy, the time complexity is O(n) because you only iterate through the array of piles once. The space complexity is O(1) since only a single variable is used to maintain the cumulative XOR.

Ready to solve this problem?

Practice Game of Nim with our built-in code editor and test cases.

Practice on FleetCode
Previous

Subtree Removal Game with Fibonacci Tree