#810 Chalkboard XOR Game - Solution

You are given an array of integers nums represents the numbers written on a chalkboard.

Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. The bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return true if and only if Alice wins the game, assuming both players play optimally.

Example 1:

Input: nums = [1,1,2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums become [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

Example 2:

Input: nums = [0,1]
Output: true

Example 3:

Input: nums = [1,2,3]
Output: true

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] < 2¹⁶

The Chalkboard XOR Game is a classic game theory and bit manipulation puzzle. Players alternately erase numbers from the array, and if the XOR of the remaining numbers becomes 0 at the start of a player's turn, that player loses. A brute force simulation of all game states is impractical due to exponential possibilities.

The key insight comes from analyzing the properties of XOR and the structure of the game. First compute the XOR of all elements in the array. If the XOR is already 0, the first player has a winning position. Otherwise, the parity of the array length becomes important. With careful reasoning about how removing elements affects the overall XOR and turn order, we can derive a deterministic rule that decides whether the first player can force a win.

This observation allows the problem to be solved with a single pass over the array to compute the XOR value, leading to an efficient solution with minimal extra memory.

Approach	Time Complexity	Space Complexity
XOR observation with game theory insight	O(n)	O(1)

Solutions (10)

Approach 1: Mathematical Insight

The game can be reduced to a theoretical observation: Alice will win if the XOR of all elements of the array (before any move) is already 0 or if the length of the array is even. This is because, under optimal play, a XOR of 0 or an even number of moves ensures Alice's win. When it's an even number, Bob will be the one forced to make a move that reduces the XOR to 0 if possible.

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as no extra space is used beyond a few variables.

Python C++Java C#JavaScript

1using System;
2
3public class Solution {
4    public bool XorGame(int[] nums) {
5        int xorSum = 0;
6        foreach (int num in nums) {
7            xorSum ^= num;
8        }
9        return xorSum == 0 || nums.Length % 2 == 0;
10    }
11}

Explanation

The C# solution uses a foreach loop to calculate the XOR of all nums. If the XOR is zero or the length of nums is even, Alice wins.

Approach 2: Dynamic Programming

This approach builds upon understanding the subproblems of removing each number and calculating the XOR of the remaining elements. Even though its complexity is higher, this method helps us understand more granular moves and outcomes if not assuming mathematical shortcuts.

Time Complexity: O(2^n) due to the exponential number of XOR states possible.
Space Complexity: O(n), largely dictated by function call stack depth.

Python C++Java C#JavaScript

1#include <vector>
2#include <unordered_map>
using namespace std;

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        return canWin(nums, xorSum, 0);
    }
private:
    unordered_map<string, bool> memo;
    bool canWin(vector<int>& nums, int xorSum, int mask) {
        if (xorSum == 0) return false;
        string mkey = hashKey(mask, nums.size());
        if (memo.find(mkey) != memo.end()) return memo[mkey];
        for (int i = 0; i < nums.size(); ++i) {
            if (!(mask & (1 << i))) {
                if (!canWin(nums, xorSum ^ nums[i], mask | (1 << i))) {
                    return memo[mkey] = true;
                }
            }
        }
        return memo[mkey] = false;
    }
    string hashKey(int mask, int n) {
        return to_string(mask) + "#" + to_string(n);
    }
};