LeetCode 810: Chalkboard XOR Game

Problem Restatement

We are given an array nums of non-negative integers written on a chalkboard.

Alice and Bob take turns erasing exactly one number. Alice moves first.

After a player erases a number, if the XOR of all remaining numbers becomes 0, that player loses.

There is one special rule: if a player starts their turn and the XOR of all numbers is already 0, that player wins immediately.

Return True if Alice wins with optimal play. Otherwise, return False. The official constraints include 1 <= nums.length <= 1000 and 0 <= nums[i] <= 2^16.

Input and Output

Examples

Example 1:

nums = [1, 1, 2]

The total XOR is:

1 ^ 1 ^ 2 = 2

Alice has two meaningful choices.

If Alice erases 2, the remaining numbers are:

[1, 1]

Their XOR is:

1 ^ 1 = 0

So Alice loses immediately.

If Alice erases 1, the remaining numbers are:

[1, 2]

Their XOR is not 0, so Bob moves next. Bob can then force Alice to erase the last number and lose.

So the answer is:

False

Example 2:

nums = [0, 1]

The array length is even, so Alice has a winning strategy.

The answer is:

True

Example 3:

nums = [1, 2, 3]

The total XOR is:

1 ^ 2 ^ 3 = 0

Alice starts her turn with total XOR already equal to 0, so she wins immediately.

The answer is:

True

First Thought: Game Search

A direct game solution would try every possible number Alice can erase, then every possible number Bob can erase, and so on.

This creates a game tree.

At each step, there may be many choices, so the number of possible games grows very quickly. With up to 1000 numbers, this is impossible.

We need to use the structure of XOR and the parity of the number of elements.

Key Insight

Let:

x = nums[0] ^ nums[1] ^ ... ^ nums[n - 1]

There are two simple winning cases for Alice:

x == 0

or:

len(nums) % 2 == 0

So the final answer is:

x == 0 or len(nums) % 2 == 0

The first case follows directly from the rule: if Alice starts with XOR 0, Alice wins immediately.

The second case is the main observation. If the number of elements is even and the total XOR is not 0, Alice can always make a move that does not immediately lose. After Alice removes one number, Bob faces an odd number of elements. With optimal play, the parity structure favors Alice.

If the number of elements is odd and total XOR is not 0, Alice loses under optimal play.

Why Even Length Wins

Assume the current array length is even and total XOR is not 0.

Suppose every possible move made the remaining XOR equal to 0.

If Alice removes nums[i], the remaining XOR is:

x ^ nums[i]

For that to be 0, we would need:

nums[i] == x

for every index i.

That means every number would equal x.

But there are an even number of elements. XORing the same value an even number of times gives 0, contradicting the assumption that the total XOR is not 0.

Therefore, at least one move does not lose immediately.

This argument is the reason even-length non-zero-XOR positions are winning.

Algorithm

Compute the XOR of all numbers:

total = 0
for num in nums:
    total ^= num

Then return:

total == 0 or len(nums) % 2 == 0

Correctness

If total == 0, Alice wins immediately by the problem rule, so the algorithm correctly returns True.

Now suppose total != 0.

If len(nums) is even, the argument above shows Alice has at least one move that does not immediately lose. After Alice makes such a move, Bob receives an odd-length position. The same parity argument implies Bob cannot avoid eventually giving Alice a winning position. Thus Alice wins, so the algorithm correctly returns True.

If len(nums) is odd and total != 0, Alice must move to an even-length position. If her move makes the remaining XOR 0, she loses immediately. Otherwise, Bob receives an even-length non-zero-XOR position, which is winning for the player to move. Therefore Bob wins, and Alice loses. The algorithm correctly returns False.

Thus the algorithm returns True exactly when Alice has a winning strategy.

Complexity

Let n = len(nums).

Implementation

class Solution:
    def xorGame(self, nums: list[int]) -> bool:
        total = 0

        for num in nums:
            total ^= num

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

Code Explanation

The variable total stores the XOR of all numbers:

total = 0

XOR with 0 leaves a number unchanged, so this is the correct starting value.

We update it with every number:

for num in nums:
    total ^= num

After the loop, total is the XOR of the whole chalkboard.

Then we apply the theorem:

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

Alice wins if the starting XOR is already 0, or if the number of elements is even.

Testing

def run_tests():
    s = Solution()

    assert s.xorGame([1, 1, 2]) is False
    assert s.xorGame([0, 1]) is True
    assert s.xorGame([1, 2, 3]) is True
    assert s.xorGame([1]) is False
    assert s.xorGame([0]) is True
    assert s.xorGame([5, 5]) is True

    print("all tests passed")

run_tests()