Problem Description

The Chalkboard XOR Game is a two-player game played with an array of positive integers called nums. Players take turns erasing exactly one number from the chalkboard. The key rule is: after each erasure, if the bitwise XOR (exclusive OR) of all remaining numbers is zero, the player who just made the move loses the game.

• The first player moves first.
• Both players play optimally (make the best possible moves).
• The game continues until there are no numbers left or a player loses by leaving the XOR as zero.

The task is: given the initial array nums, determine if the first player can guarantee a win, assuming both play optimally.

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] < 2^16

Thought Process

At first glance, this problem seems to require simulating each possible move and checking the XOR after every erasure, which would be extremely inefficient for large arrays. The challenge is to determine if the first player can always force a win, regardless of the opponent's actions.

Let's think about how the XOR behaves:

• After each move, the set of numbers changes, and so does the XOR.
• If the XOR is zero at the start of a player's turn, that player is in a "losing" position: any move will make the XOR nonzero for the opponent, who can then always respond optimally.
• If the XOR is nonzero, the player can try to erase a number to make the XOR zero for the opponent, but this is not always possible.

The key is to analyze the initial XOR and the parity (even or odd) of the number of elements.

Solution Approach

Let's break down the solution step by step:

1. Compute the XOR of all numbers:
   • Let xorSum be the XOR of all elements in nums.
2. Check the initial state:
   • If xorSum == 0, the first player wins immediately, because the opponent starts with a "losing" position (any move they make gives a nonzero XOR to the next player).
3. Analyze the parity of the array length:
   • If the number of elements is even, the first player can always win by mirroring the opponent's moves (like in Nim).
   • If the number of elements is odd and xorSum != 0, the second player can always mirror the first player's moves and force a win.
4. Final Rule:
   • The first player wins if either xorSum == 0 or the number of elements is even.
   • Otherwise, the first player loses.

Why does this work? If the initial XOR is zero, the opponent is always forced into a nonzero situation. If the length is even, the first player can always match the opponent's moves such that the XOR never becomes zero on their turn.

Example Walkthrough

Example Input: nums = [1, 1, 2]

1. Compute XOR: 1 ^ 1 ^ 2 = 0 ^ 2 = 2
2. Number of elements: 3 (odd)
3. Check conditions:
   • xorSum != 0 (it's 2)
   • Number of elements is odd
   So, the first player cannot guarantee a win.

Example Input 2: nums = [1, 2, 3, 4]

1. Compute XOR: 1 ^ 2 ^ 3 ^ 4 = 4
2. Number of elements: 4 (even)
3. Check conditions:
   • Even length, so the first player can always win.

Code Implementation

class Solution:
    def xorGame(self, nums):
        xor_sum = 0
        for num in nums:
            xor_sum ^= num
        return xor_sum == 0 or len(nums) % 2 == 0
      

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        int xor_sum = 0;
        for (int num : nums) xor_sum ^= num;
        return xor_sum == 0 || nums.size() % 2 == 0;
    }
};
      

class Solution {
    public boolean xorGame(int[] nums) {
        int xorSum = 0;
        for (int num : nums) xorSum ^= num;
        return xorSum == 0 || nums.length % 2 == 0;
    }
}
      

var xorGame = function(nums) {
    let xorSum = 0;
    for (let num of nums) xorSum ^= num;
    return xorSum === 0 || nums.length % 2 === 0;
};
      

Time and Space Complexity

Brute-force approach: Simulating all possible moves would require checking every possible subset after each erasure, leading to exponential time complexity: O(2^n).

Optimized solution:

• Time complexity: O(n) — We only need to iterate through the array once to compute the XOR.
• Space complexity: O(1) — Only a constant amount of extra space is used for the XOR sum.

Summary

The Chalkboard XOR Game is a variation of the Nim game where the goal is to avoid leaving a zero XOR after your move. The elegant solution comes from recognizing the relationship between the initial XOR and the parity of the array's length. If the initial XOR is zero or the number of elements is even, the first player can always guarantee a win by playing optimally. This insight allows us to solve the problem with a simple linear scan and a single logical check, making the solution both efficient and easy to implement.