810. Chalkboard XOR Game Solution

Q: Is Chalkboard XOR Game easy or hard?

The problem is labeled Hard because the winning strategy is not obvious from simulation. Many candidates attempt recursion or DP over game states before discovering the XOR parity rule. Once the mathematical insight is known, the implementation becomes very short.

Q: Chalkboard XOR Game Python/Java solution

In both Python and Java, the implementation simply computes the XOR of all array elements and checks the array length. Return true if the XOR is 0 or if the array length is even. The logic is identical across Python, Java, C++, C#, and JavaScript.

Q: How to solve Chalkboard XOR Game in O(n)?

Compute the XOR of all numbers in the array. If the XOR equals 0, Alice wins because the opponent is forced into a losing state. If the XOR is non-zero, Alice wins only when the number of elements is even. This logic allows the problem to be solved with one iteration over the array.

Q: What is the best approach for Chalkboard XOR Game?

The optimal approach uses a mathematical observation based on XOR properties. If the XOR of all numbers is 0, Alice wins immediately. Otherwise, Alice wins if the array length is even. This reduces the solution to a single pass XOR computation with O(n) time and O(1) space.

Q: Is Chalkboard XOR Game asked at Google/Amazon/Meta?

Chalkboard XOR Game is a classic XOR and game theory puzzle commonly seen in advanced algorithm practice sets. Variants of XOR-based game problems appear in interviews at companies like Google and Meta because they test reasoning about invariants and optimal play.

Q: What data structure is used in Chalkboard XOR Game?

The optimal solution does not require complex data structures. It relies on XOR accumulation over an array and reasoning about parity. A theoretical dynamic programming version may use bitmasks and memoization to represent subsets of the array.

Q: What is the time complexity of Chalkboard XOR Game?

The optimal mathematical solution runs in O(n) time because it computes the XOR of all elements once. Space complexity is O(1) since only a few variables are needed. A brute-force dynamic programming approach that explores game states can take O(n * 2^n) time.

The problem

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¹⁶

Approach overview

Problem Overview: You are given an array of integers written on a chalkboard. Two players take turns erasing one number. If the XOR of the remaining numbers becomes 0 immediately after a move, the player who made that move loses. Both players play optimally. The task is to determine whether Alice (the first player) can guarantee a win.

Approach 1: Mathematical Insight (O(n) time, O(1) space)

The key observation comes from properties of XOR and optimal play in game theory. Compute the XOR of all elements in the array. If the XOR is already 0, Alice wins immediately because any move she makes forces Bob into a losing configuration. If the XOR is non-zero, the parity of the array length becomes critical. When the number of elements is even, Alice can always remove a number while keeping the total XOR non-zero, forcing Bob into the dangerous state. When the array length is odd and the XOR is non-zero, every possible move risks leaving a zero XOR for the opponent to exploit. The algorithm simply computes the total XOR using a single pass through the array and checks the array length parity. This approach leverages properties of bit manipulation and avoids exploring game states entirely.

Approach 2: Dynamic Programming (State Exploration) (O(n * 2^n) time, O(2^n) space)

A more direct way to reason about the game is to simulate all possible states. Represent the remaining numbers as a bitmask where each bit indicates whether a number is still on the board. For each state, compute the XOR of active elements and try removing each available number. If any removal leads to a state where the opponent loses, the current state is winning. Memoization stores results for each mask to avoid recomputation. This turns the exponential search tree into a manageable DP over subsets. The approach clearly models the game mechanics but becomes expensive as n grows because the state space contains 2^n subsets. It demonstrates how brute-force game analysis works before discovering the mathematical shortcut.

Recommended for interviews: The mathematical insight approach is what interviewers typically expect. It reduces the entire game to two quick checks: compute the XOR of all numbers and inspect whether the array length is even. Explaining the DP or recursive game simulation first can show your reasoning process, but recognizing the XOR parity pattern demonstrates strong understanding of mathematical reasoning and competitive programming tricks.

Approach 1: 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.

Python

def xorGame(nums):
    return reduce(lambda x, y: x ^ y, nums) == 0 or len(nums) % 2 == 0

Java

import java.util.*;

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

C++

#include <vector>
using namespace std;

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

JavaScript

function xorGame(nums) {
    let xorSum = nums.reduce((acc, num) => acc ^ num, 0);
    return xorSum === 0 || nums.length % 2 === 0;
}

using System;

public class Solution {
    public bool XorGame(int[] nums) {
        int xorSum = 0;
        foreach (int num in nums) {
            xorSum ^= num;
        }
        return xorSum == 0 || nums.Length % 2 == 0;
    }
}

The solution checks if the XOR of the entire list is already zero or if the list length is even. If either condition is met, Alice wins. We use Python's reduce function to calculate the XOR of the nums list.

Complexity

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.

Try this approach in the editor

Approach 2: 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.

Python

def xorGame(nums):
    from functools import lru_cache
    
    @lru_cache(None)
    def canWin(xorSum, remaining):
        if xorSum == 0:
            return False
        for i, num in enumerate(remaining):
            if not canWin(xorSum ^ num, remaining[:i] + remaining[i+1:]):
                return True
        return False
    xor_sum = 0
    for num in nums:
        xor_sum ^= num
    return canWin(xor_sum, tuple(nums))

Java

import java.util.*;

class Solution {
    private Map<String, Boolean> memo = new HashMap<>();

    public boolean xorGame(int[] nums) {
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }
        return canWin(nums, xorSum, 0);
    }

    private boolean canWin(int[] nums, int xorSum, int mask) {
        if (xorSum == 0) return false;
        String key = mask + "#" + nums.length;
        if (memo.containsKey(key)) return memo.get(key);
        for (int i = 0; i < nums.length; i++) {
            if ((mask & (1 << i)) == 0) {
                if (!canWin(nums, xorSum ^ nums[i], mask | (1 << i))) {
                    memo.put(key, true);
                    return true;
                }
            }
        }
        memo.put(key, false);
        return false;
    }
}

C++

#include <vector>
#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);
    }
};

JavaScript

function xorGame(nums) {
    const memo = new Map();

    function canWin(nums, xorSum, mask) {
        if (xorSum === 0) return false;
        const mkey = mask + '#' + nums.length;
        if (memo.has(mkey)) return memo.get(mkey);
        for (let i = 0; i < nums.length; ++i) {
            if (!(mask & (1 << i))) {
                if (!canWin(nums, xorSum ^ nums[i], mask | (1 << i))) {
                    memo.set(mkey, true);
                    return true;
                }
            }
        }
        memo.set(mkey, false);
        return false;
    }

    const xorSum = nums.reduce((acc, num) => acc ^ num, 0);
    return canWin(nums, xorSum, 0);
}

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<string, bool> memo = new Dictionary<string, bool>();

    public bool XorGame(int[] nums) {
        int xorSum = 0;
        foreach (int num in nums) {
            xorSum ^= num;
        }
        return CanWin(nums, xorSum, 0);
    }

    private bool CanWin(int[] nums, int xorSum, int mask) {
        if (xorSum == 0) return false;
        string key = mask + "#" + nums.Length;
        if (memo.ContainsKey(key)) return memo[key];
        for (int i = 0; i < nums.Length; i++) {
            if ((mask & (1 << i)) == 0) {
                if (!CanWin(nums, xorSum ^ nums[i], mask | (1 << i))) {
                    memo[key] = true;
                    return true;
                }
            }
        }
        memo[key] = false;
        return false;
    }
}

The dynamic programming approach uses recursion with memoization to explore different outcomes of removing each number from nums. If removing any number of remaining results in a lose state (`xorSum` becomes zero), the current player loses.

Complexity

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.

Try this approach in the editor

Approach 3: Bit Manipulation

According to the game rules, if the XOR result of all numbers on the blackboard is 0 when it is a player's turn, that player wins. Since Alice goes first, if the XOR result of all numbers in nums is 0, Alice can win.

When the XOR result of all numbers in nums is not 0, let's analyze Alice's winning situation based on the parity of the length of the array nums.

When the length of nums is even, if Alice is destined to lose, there is only one situation: no matter which number Alice erases, the XOR result of all remaining numbers equals 0. Let's analyze whether this situation exists.

Assume the length of the array nums is n, and n is even. Let the XOR result of all numbers be S, then:

$S = nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1] neq 0

Let S_i be the XOR result after erasing the i-th number from the array nums, then:

S_i \oplus nums[i] = S

XOR both sides of the equation by nums[i], we get:

S_i = S \oplus nums[i]

If no matter which number Alice erases, the XOR result of all remaining numbers equals 0, then for all i, we have S_i = 0, i.e.,

S_0 \oplus S_1 \oplus cdots \oplus S_{n-1} = 0

Substitute S_i = S \oplus nums[i] into the above equation, we get:

S \oplus nums[0] \oplus S \oplus nums[1] \oplus cdots \oplus S \oplus nums[n-1] = 0

There are n (even) S terms in the above equation, and nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1] also equals S, so the equation is equivalent to 0 \oplus S = 0. This contradicts S neq 0, so this situation does not exist. Therefore, when the length of nums is even, Alice is guaranteed to win.

If the length is odd, then after Alice erases a number, the remaining numbers are even in length, leaving Bob with an even-length situation, which means Bob is guaranteed to win, and thus Alice is destined to lose.

In conclusion, Alice can win when the length of nums is even or the XOR result of all numbers in nums is 0.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.

func xorGame(nums []int) bool {
	if len(nums)%2 == 0 {
		return true
	}
	x := 0
	for _, v := range nums {
		x ^= v
	}
	return x == 0
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Mathematical Insight	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.
Approach 2: Dynamic Programming	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.
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Mathematical Insight	O(n)	O(1)	Optimal solution for interviews and production; relies on XOR parity observation
Dynamic Programming (State Mask)	O(n * 2^n)	O(2^n)	Useful for understanding the game mechanics or validating the mathematical insight

Frequently asked questions

Is Chalkboard XOR Game easy or hard?

The problem is labeled Hard because the winning strategy is not obvious from simulation. Many candidates attempt recursion or DP over game states before discovering the XOR parity rule. Once the mathematical insight is known, the implementation becomes very short.

Chalkboard XOR Game Python/Java solution

In both Python and Java, the implementation simply computes the XOR of all array elements and checks the array length. Return true if the XOR is 0 or if the array length is even. The logic is identical across Python, Java, C++, C#, and JavaScript.

How to solve Chalkboard XOR Game in O(n)?

Compute the XOR of all numbers in the array. If the XOR equals 0, Alice wins because the opponent is forced into a losing state. If the XOR is non-zero, Alice wins only when the number of elements is even. This logic allows the problem to be solved with one iteration over the array.

What is the best approach for Chalkboard XOR Game?

The optimal approach uses a mathematical observation based on XOR properties. If the XOR of all numbers is 0, Alice wins immediately. Otherwise, Alice wins if the array length is even. This reduces the solution to a single pass XOR computation with O(n) time and O(1) space.

Is Chalkboard XOR Game asked at Google/Amazon/Meta?

Chalkboard XOR Game is a classic XOR and game theory puzzle commonly seen in advanced algorithm practice sets. Variants of XOR-based game problems appear in interviews at companies like Google and Meta because they test reasoning about invariants and optimal play.

What data structure is used in Chalkboard XOR Game?

The optimal solution does not require complex data structures. It relies on XOR accumulation over an array and reasoning about parity. A theoretical dynamic programming version may use bitmasks and memoization to represent subsets of the array.

What is the time complexity of Chalkboard XOR Game?

The optimal mathematical solution runs in O(n) time because it computes the XOR of all elements once. Space complexity is O(1) since only a few variables are needed. A brute-force dynamic programming approach that explores game states can take O(n * 2^n) time.

Chalkboard XOR Game solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Mathematical Insight

Approach 2: Approach 2: Dynamic Programming

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Chalkboard XOR Game solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Mathematical Insight

Approach 2: Approach 2: Dynamic Programming

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems