Problem Statement

The Game of Nim is a straightforward two-player game played with piles of stones. The game starts with n piles of stones, labeled 0 through n-1. Each pile has size piles[i]. The two players take turns, with player 1 going first. On each turn, the current player removes any non-zero amount of stones from one of the piles.

The player who removes the last stone from a pile wins the round. If both players play optimally (i.e., making the best possible move), determine the winner of the game.

Solution

The solution to this problem uses the concept of bitwise XOR. Let's understand this concept with an example: Suppose we have two numbers a = 5 and b = 9, and we want to find their bitwise XOR.

a = 101 (binary representation) b = 1001 (binary representation)

a^b = 1100 (binary representation) = 12 (decimal representation)

The XOR operation is applied bit by bit to the two binary numbers, and the resulting binary string is converted to decimal.

Now, let's focus on the game of Nim. If we take the XOR of all the piles' sizes, we get a unique number. Let's call this number "nim_sum." If nim_sum is 0, Player 2 always wins. Otherwise, Player 1 can win.

The reason behind this is as follows:

• If nim_sum is not equal to 0, there exists at least one pile with a size that differs from the nim_sum in its binary representation. Player 1 can remove stones from this pile such that the resulting nim_sum is equal to the bit-wise XOR of the original nim_sum with the size of the pile. This ensures that nim_sum becomes 0 eventually, and therefore, Player 1 wins.
• On the other hand, if nim_sum is equal to 0, it means that all the piles' sizes have the same binary representation. In this case, any move made by Player 1 results in a non-zero nim_sum. Therefore, Player 2 always wins.

Let's see the implementation of this algorithm.

Algorithm

1. Calculate the nim_sum of all the piles' sizes by taking the XOR of all the sizes.
2. If nim_sum is equal to 0, Player 2 wins.
3. Otherwise, Player 1 wins.

The code for this algorithm in Python is as follows:

class Solution: def xorGame(self, nums: List[int]) -> bool: nim_sum = 0 for num in nums: nim_sum ^= num

    return nim_sum == 0 or len(nums) % 2 == 0
    

Time Complexity: O(n)

Space Complexity: O(1)

We have used an XOR operator to calculate the nim_sum in O(n) time, where n is the number of piles. The space complexity of the solution is O(1) since we only use a variable to store the nim_sum.

1