We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Nim Game

Number: 292

Difficulty: Easy

Paid? No

Companies: Microsoft, Google, Adobe

Problem Description

Given a heap of n stones, two players take turns removing 1 to 3 stones. You go first, and the player who removes the last stone wins. Determine if you can win the game assuming both players play optimally.

Key Insights

  • The optimal strategy depends on the number of stones modulo 4.
  • If n is a multiple of 4, no matter how many stones you remove (1, 2, or 3), your opponent can always adjust their move to leave a multiple of 4 for you, eventually forcing a win.
  • If n is not a multiple of 4, you can remove enough stones on your first move to force the remaining count to be a multiple of 4 for your opponent.

Space and Time Complexity

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

Solution

The core of the solution is the observation that if the number of stones n is divisible by 4, the first player will always lose if both players play optimally. This is because no matter the move made by the first player, the opponent can always subtract a number of stones such that the sum of the stones removed in both turns equals 4, hence preserving the multiple-of-4 condition for the first player's subsequent turn. If n is not a multiple of 4, the first player can remove the remainder (n % 4) on their first move, forcing the opponent into the losing position. The problem requires a simple constant-time modulo operation to make the decision.

Code Solutions

# Python solution for Nim Game
class Solution:
    def canWinNim(self, n: int) -> bool:
        # If n is a multiple of 4, the first player loses.
        return n % 4 != 0
← Back to All Questions