Skip to main content
Talentd

Nim Game - Solution & Explanation

EasyMathBrainteaserGame Theory16 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You are playing the following Nim Game with your friend:

  • Initially, there is a heap of stones on the table.
  • You and your friend will alternate taking turns, and you go first.
  • On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
  • The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

 

Example 1:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:

Input: n = 1
Output: true

Example 3:

Input: n = 2
Output: true

 

Constraints:

  • 1 <= n <= 231 - 1

Approach Overview

Problem Overview: You are given n stones in a pile. Two players take turns removing 1 to 3 stones. Whoever removes the last stone wins. Both players play optimally. The task is to determine if the first player can guarantee a win for a given n.

Approach 1: Dynamic Programming (O(n) time, O(n) space)

Start by modeling the game as a sequence of states where dp[i] represents whether the current player can win with i stones remaining. From state i, the player can remove 1, 2, or 3 stones, moving the opponent to i-1, i-2, or i-3. If any of those states is losing for the opponent, then dp[i] is winning. Initialize base cases: dp[1], dp[2], and dp[3] are winning states because the player can take all stones. Iterate from 4 up to n and compute the state based on the previous three values. This approach builds intuition for impartial games and mirrors typical dynamic programming reasoning, but it requires linear space and time.

Approach 2: Observation-Based Mathematical Approach (O(1) time, O(1) space)

Once you list the first few DP states, a pattern emerges: losing positions occur when the number of stones is a multiple of 4. If n = 4, every move (removing 1, 2, or 3 stones) leaves 3, 2, or 1 stones for the opponent—each a winning state for them. The same logic repeats for 8, 12, 16.... When n % 4 == 0, the first player loses because every move gives the opponent a winning configuration. When n % 4 != 0, the first player can remove n % 4 stones to force the opponent into a multiple-of-4 state and maintain that invariant for the rest of the game.

This observation turns the entire problem into a single modulus check: return false if n % 4 == 0, otherwise return true. The reasoning comes from classic game theory analysis combined with simple math. No simulation or recursion is required.

Recommended for interviews: Interviewers expect the mathematical observation. Starting with the DP formulation shows you understand state transitions and optimal play. Recognizing the repeating pattern and reducing the solution to n % 4 demonstrates strong analytical skills and familiarity with classic game-theory problems.

Approach 1: Observation-Based Mathematical Approach

In this approach, the key observation is that if n is a multiple of 4, you will lose the game if both play optimally. Hence, you can immediately return false in this case. The reason is that no matter what you do (removing 1 to 3 stones), you will leave the opponent with a number of stones that are not a multiple of 4, enabling them to adjust their removal so that you fail.

The code checks the remainder of n divided by 4. If the remainder is not zero, you can win; otherwise, you lose.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1).
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

A more generalized approach can be a dynamic programming technique to solve the problem for smaller values and build up the solution by using previously solved values. This approach can be used when learning optimal sub-structure is more relevant and the pattern is not known beforehand.

This C solution uses a cyclic buffer to store states and computes dynamically from known base conditions. The buffer size is 4 because we only need the last 3 results to compute the current state.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1) due to constant space usage.
However, it is important to note for large n, this specific approach might be constrained by array size limitations in practice.

Try this approach in the editor →

Approach 3: Finding the Pattern

The first player who gets a multiple of 4 (i.e., n can be divided by 4) will lose the game.

Proof:

  1. When n \lt 4, the first player can directly take all the stones, so the first player will win the game.
  2. When n = 4, no matter whether the first player chooses 1, 2, 3, the second player can always choose the remaining number, so the first player will lose the game.
  3. When 4 \lt n \lt 8, i.e., n = 5, 6, 7, the first player can correspondingly reduce the number to 4, then the "death number" 4 is given to the second player, and the second player will lose the game.
  4. When n = 8, no matter whether the first player chooses 1, 2, 3, it will leave a number between 4 \lt n \lt 8 to the second player, so the first player will lose the game.
  5. ...
  6. By induction, when a player gets the number n, and n can be divided by 4, he will lose the game, otherwise, he will win the game.

The time complexity is O(1), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Observation-Based Mathematical Approach

Time Complexity: O(1).
Space Complexity: O(1).

Dynamic Programming Approach

Time Complexity: O(n).
Space Complexity: O(1) due to constant space usage.
However, it is important to note for large n, this specific approach might be constrained by array size limitations in practice.

Finding the Pattern—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(n)O(n)When deriving the pattern or explaining optimal game state transitions
Observation-Based Mathematical ApproachO(1)O(1)Best for production or interviews once the n % 4 insight is recognized

Video Solution

Nim Game (LeetCode #292) • Programmer Mitch • 13,096 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Nim Game easy or hard?
Nim Game is categorized as an easy problem on most platforms. The coding portion is trivial, but recognizing the n % 4 pattern requires understanding optimal play and basic game theory reasoning.
Nim Game Python/Java solution
In Python or Java, the implementation is typically a single condition: return n % 4 != 0. This constant-time check directly applies the mathematical observation that multiples of four are losing positions for the starting player.
How to solve Nim Game in O(1)?
Compute n % 4. If the result is 0, return false because the opponent can mirror every move and eventually take the last stone. If the result is not 0, return true since the first player can remove n % 4 stones and force the game into a losing multiple-of-4 state for the opponent.
What is the best approach for Nim Game?
The optimal approach uses a mathematical observation: the first player loses only when n is a multiple of 4. If n % 4 == 0, every possible move gives the opponent a winning position. Otherwise, the first player can force a win by removing n % 4 stones and maintaining the multiple-of-4 pattern.
Is Nim Game asked at Google/Amazon/Meta?
Nim Game represents a classic game theory puzzle frequently used in technical interviews at companies like Google, Amazon, and Meta. Interviewers use it to test mathematical reasoning, pattern recognition, and the ability to derive an optimal strategy from smaller states.
What data structure is used in Nim Game?
The optimal solution does not require any data structure because it relies on a mathematical property of the game. A dynamic programming variant uses an array dp[i] to track whether a position with i stones is winning or losing.
What is the time complexity of Nim Game?
The optimal solution runs in O(1) time and O(1) space because it only checks whether n % 4 equals zero. A dynamic programming approach exists with O(n) time and O(n) space, but it is mainly useful for discovering the pattern.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Flip Game II