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

Game of Nim

Number: 2062

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Alice and Bob play a game with n piles of stones. Each turn, a player removes any positive number of stones from any non-empty pile. Alice moves first. The player who is unable to make a move loses. Given the array of piles, determine if Alice, playing optimally, can guarantee a win.

Key Insights

  • This is a classic Nim game.
  • The key is to compute the Nim-sum (bitwise XOR of the counts in the piles).
  • If the Nim-sum is non-zero, the first player (Alice) can force a win; if it is zero, Bob wins.
  • The solution involves a simple linear pass over the piles array.

Space and Time Complexity

Time Complexity: O(n) because we iterate through the list of piles once. Space Complexity: O(1) as we only use a constant amount of extra space.

Solution

The problem is solved using principles from the Nim game. The idea is to calculate the XOR (also known as the Nim-sum) of all the piles. If the result is non-zero, it means the current player (Alice) can force a win with optimal play. Otherwise, the second player (Bob) wins because any move by Alice will leave a non-zero Nim-sum for Bob. We use a simple loop to compute the Nim-sum which directly gives us the answer.

Code Solutions

# Function to determine if Alice wins
def nimGame(piles):
    nim_sum = 0  # Initialize nim sum to 0
    # Compute the nim sum by XORing all the pile values
    for stones in piles:
        nim_sum ^= stones  # XOR operation on the pile value
    # If nim sum is non-zero, Alice can force a win
    return nim_sum != 0

# Example usage:
piles = [1, 2, 3]
print(nimGame(piles))  # Expected output: False (as Bob wins)
← Back to All Questions