Domain 1EasyCORE

Nim Game

The Nim Game involves two players taking turns removing 1 to 3 stones from a heap. The player who removes the last stone wins. Given an integer `n` representing the number of stones in the heap, determine if the first player can win assuming both players play optimally.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Brainteaser#Minimax

292. Nim Game

Model: qwen2.5-coder:14b
Topics: Brainteaser,Minimax
FAANG asked: 0
Acceptance rate: 55.1%


Problem Breakdown

The Nim Game involves two players taking turns removing 1 to 3 stones from a heap. The player who removes the last stone wins. Given an integer n representing the number of stones in the heap, determine if the first player can win assuming both players play optimally.

Inputs:

  • An integer n, where 1 <= n <= 2^31 - 1.

Outputs:

  • A boolean value: true if the first player can win, otherwise false.

Implicit Constraints or Tricky Edge Cases:

  • If n is very large (close to 2^31 - 1), ensure the solution handles it efficiently.
  • Consider edge cases where n is 1, 2, or 3, as these are simple scenarios that can reveal patterns.

Intuition

A brute-force approach would involve simulating all possible moves and outcomes recursively. However, this approach is computationally expensive with a time complexity of O(4^n), which is infeasible for large n.

The key insight is to recognize a pattern in the game:

  • If n is a multiple of 4, no matter how many stones (1 to 3) the first player removes, the second player can always adjust their move to ensure that the number of stones left is again a multiple of 4 after their turn. This cycle continues until the first player is forced to take the last stone and lose.
  • If n is not a multiple of 4, the first player can always remove enough stones (1 to 3) to make the remaining stones a multiple of 4 for the second player. This puts the second player in the losing position described above.

Approach

Based on the insight, we can determine the winner by checking if n is a multiple of 4:

  • If n % 4 == 0, return false (the first player cannot win).
  • Otherwise, return true (the first player can win).

This approach leverages constant time and space complexity.

Complexity Analysis

  • Time Complexity: O(1) - The solution involves a single modulus operation.
  • Space Complexity: O(1) - No additional data structures are used.

Solution

def canWinNim(n: int) -> bool:
    return n % 4 != 0

Edge Cases Handled

  • n = 1, 2, 3: The first player wins by taking all stones.
  • n = 4: The first player loses if both play optimally.
  • Large n (close to 2^31 - 1): The solution handles large values efficiently due to constant time complexity.