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.

Description Hints 1 Solution Video 4:17

292. Nim Game

Easy60.6% acceptance6 companies

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: