Problem Description

The Game of Nim is a classic mathematical game of strategy. In this problem, you are given a list called piles, where each element represents the number of stones in a separate pile. Two players take turns; on each turn, a player can remove any positive number of stones from a single pile. The player who removes the last stone wins the game.

You are asked to determine whether the first player (the one who starts the game) can guarantee a win, assuming both players play optimally.

• The input is an array piles of positive integers.
• Return True if the first player can force a win, False otherwise.
• There is one valid answer for each input.
• Do not modify the input array.

Thought Process

At first glance, you might consider simulating every possible move for both players, recursively checking all game states. However, this brute-force approach is extremely inefficient, especially as the number of piles or stones increases.

To optimize, we look for patterns or mathematical properties. The Game of Nim is well-known in combinatorial game theory, and it has a famous solution based on the bitwise XOR operation. The key insight is that, instead of tracking every possible move, you can use the XOR of all pile sizes to determine whether the first player can win.

The challenge lies in recognizing this pattern and understanding why XOR works for this game.

Solution Approach

The solution relies on the Nim-sum, which is the XOR of all pile sizes. Here's why and how we use it:

1. Compute the Nim-sum: Calculate the XOR of all the elements in piles.
2. Interpret the Result:
   • If the Nim-sum is zero, the first player cannot win if both play optimally.
   • If the Nim-sum is non-zero, the first player can win by always moving to a state where the Nim-sum is zero after their turn.
3. Why XOR? The XOR operation models the parity and interactions between the piles. If the combined parity (Nim-sum) is zero, the current player is in a losing position; otherwise, they are in a winning position.
4. Implementation: Loop over the piles array, XOR-ing each element together. Return True if the result is not zero, False otherwise.

This approach is efficient and elegant, requiring only a single pass through the array and constant space.

Example Walkthrough

Let's consider the input piles = [3, 4, 5].

1. Compute the Nim-sum:
   • Start with 0.
   • 0 XOR 3 = 3
   • 3 XOR 4 = 7
   • 7 XOR 5 = 2
   So, the Nim-sum is 2.
2. Since the Nim-sum is not zero, the first player can guarantee a win with optimal play.
3. If the input were piles = [1, 1]:
   • 0 XOR 1 = 1
   • 1 XOR 1 = 0
   Now, the Nim-sum is 0, so the first player cannot win.

Time and Space Complexity

• Brute-force approach: Simulating all possible moves recursively leads to exponential time complexity, specifically O(kⁿ) where n is the number of piles and k is the maximum number of stones in a pile.
• Optimized (Nim-sum) approach:
  • Time Complexity: O(n), where n is the number of piles, as we simply iterate through the array once.
  • Space Complexity: O(1), since we only use a single integer to store the Nim-sum.

Summary

The Game of Nim is a beautiful example of how mathematical insight can turn an intractable brute-force problem into an elegant, efficient solution. By recognizing the significance of the XOR operation (Nim-sum), we can instantly determine the winning strategy for the first player. This approach is efficient, easy to implement, and highlights the power of pattern recognition in algorithm design.

Code Implementation

def canWinNim(piles):
    nim_sum = 0
    for pile in piles:
        nim_sum ^= pile
    return nim_sum != 0
      

class Solution {
public:
    bool canWinNim(vector<int>& piles) {
        int nim_sum = 0;
        for (int pile : piles) {
            nim_sum ^= pile;
        }
        return nim_sum != 0;
    }
};
      

class Solution {
    public boolean canWinNim(int[] piles) {
        int nimSum = 0;
        for (int pile : piles) {
            nimSum ^= pile;
        }
        return nimSum != 0;
    }
}
      

function canWinNim(piles) {
    let nimSum = 0;
    for (let pile of piles) {
        nimSum ^= pile;
    }
    return nimSum !== 0;
}