Chalkboard XOR Game
Problem
Players take turns erasing one number from the chalkboard. If erasing a number makes the XOR of remaining numbers 0, the erasing player loses. Initial XOR 0 means Alice wins. Determine if Alice (first) wins assuming optimal play.
nums = [1,1,2]falsefrom functools import reduce
from operator import xor
def xorGame(nums):
return reduce(xor, nums) == 0 or len(nums) % 2 == 0var xorGame = function(nums) {
let x = 0;
for (const v of nums) x ^= v;
return x === 0 || nums.length % 2 === 0;
};class Solution {
public boolean xorGame(int[] nums) {
int x = 0;
for (int v : nums) x ^= v;
return x == 0 || nums.length % 2 == 0;
}
}class Solution {
public:
bool xorGame(vector<int>& nums) {
int x = 0;
for (int v : nums) x ^= v;
return x == 0 || nums.size() % 2 == 0;
}
};Explanation
You might expect to simulate the whole game tree, but the winner is decided by a one-line rule: Alice wins if the XOR of all numbers is already 0, or if the array length is even.
First, if the total XOR is 0 before anyone moves, Alice has already won by the problem's own rule, so we return true immediately.
Otherwise the parity of the count decides it. When there is an even number of stones, it can be proven that Alice never has to be the one forced to make the XOR zero, so she wins. With an odd count and a non-zero XOR, every move she could make hands the loss to her, so she loses.
The code just folds all numbers with XOR into x, then returns x == 0 || nums.length % 2 == 0.
Example: nums = [1, 1, 2]. The XOR is 1 ^ 1 ^ 2 = 2, which is non-zero, and the length 3 is odd. Both conditions fail, so the result is false — Alice loses.