How do you solve Nim Game on LeetCode?

Nim Game (LeetCode #292) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: If the number of stones is a multiple of 4, the first player cannot win.

What is the brute force solution for Nim Game?

The brute force approach for Nim Game is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we simulate every possible move for both players to determine if the first player can win. This involves recursively checking all possible outcomes until we reach the base case of zero stones. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Nim Game?

Nim Game uses the following concepts: Math, Brainteaser, Game Theory. The recommended patterns to study are: Game Theory, Mathematical Patterns.

What are the interview tips for Nim Game?

Always think about the base cases first, especially in recursive problems. Look for patterns or mathematical properties that can simplify the problem. Communicate your thought process clearly, especially when transitioning from brute force to optimal solutions.

What are common mistakes when solving Nim Game?

Not recognizing the pattern of multiples of 4 and overcomplicating the solution. Failing to consider the base cases properly in the brute force approach.

#292

Nim Game

Easy

MathBrainteaserGame TheoryGame TheoryMathematical Patterns

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(1)

💡

Intuition

Time O(1)Space O(1)

The optimal solution leverages the observation that if the number of stones is a multiple of 4, the first player cannot win if both play optimally. This is because any move will leave a non-multiple of 4 for the opponent, allowing them to eventually force a win.

⚙️

Algorithm

3 steps

1Step 1: Check if n % 4 == 0.
2Step 2: If true, return false (the first player cannot win).
3Step 3: If false, return true (the first player can win).

solution.py2 lines

1def canWin(n):
2    return n % 4 != 0

ℹ

Complexity note: The time complexity is O(1) because we are only performing a single modulus operation, and space complexity is also O(1) as we are using constant space.

1If the number of stones is a multiple of 4, the first player cannot win.
2The game can be reduced to a simple mathematical check rather than simulating all moves.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.