LeetCode Problem 810

Difficulty: 🔴 Hard
Topics: Array, Math, Bit Manipulation, Brainteaser, Game Theory

Solution

LeetCode 810, Chalkboard XOR Game

Problem Understanding

This problem describes a two player game played on an array of integers. The numbers are written on a chalkboard, and players take turns erasing exactly one number. Alice moves first, then Bob, and both players play optimally.

The key rule is unusual. A player loses immediately if the act of removing a number causes the XOR of all remaining numbers to become 0.

There is also another important rule. If a player begins their turn and the XOR of all remaining numbers is already 0, then that player wins immediately.

The input is an integer array nums. Each element is a non negative integer. The task is to determine whether Alice can force a win assuming both players make optimal decisions.

The constraints are relatively small:

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

Even though the array length is only up to 1000, the game itself has exponentially many possible move sequences. A naive recursive game simulation would quickly become infeasible because every move branches into many future possibilities.

The most important thing to understand is how XOR behaves when removing elements.

Suppose the XOR of the entire array is:

total_xor = nums[0] XOR nums[1] XOR ... XOR nums[n-1]

If we remove a value x, the new XOR becomes:

new_xor = total_xor XOR x

This works because XOR cancels identical values:

a XOR a = 0

A naive implementation can easily get trapped trying to simulate all possible game states. The important edge cases are:

• Arrays whose total XOR is already 0
• Arrays with only one element
• Arrays with even length versus odd length
• Arrays where every move appears dangerous
• Arrays containing repeated numbers

These cases reveal the mathematical structure of the game.

Approaches

Brute Force Approach

The brute force solution treats the game as a complete game tree search.

At every turn:

1. Compute the current XOR of all numbers.
2. Try removing each possible element.
3. If removing an element makes the remaining XOR equal to 0, that move immediately loses.
4. Otherwise recursively determine whether the opponent can win from the resulting state.
5. If any move causes the opponent to lose, then the current player wins.

This approach is correct because it explicitly explores every possible legal sequence of moves and applies optimal play logic using minimax style recursion.

However, it is far too slow. For an array of size n, there can be up to:

n * (n-1) * (n-2) * ...

possible move sequences.

The total number of states grows factorially, which becomes impractical even for moderate input sizes.

Optimal Approach

The key insight is that the game has a surprisingly simple mathematical result.

There are only two cases:

1. If the total XOR of the array is 0, Alice immediately wins.
2. Otherwise, Alice wins if and only if the array length is even.

This result comes from game theory and XOR properties.

Suppose the current XOR is non zero.

If the array length is even, the current player can always force the game into a state where the opponent eventually faces an odd sized array with non zero XOR.

If the array length is odd and the XOR is non zero, the current player is trapped in a losing position under optimal play.

The remarkable part is that we do not need to simulate moves at all. The entire game reduces to checking:

(total_xor == 0) OR (len(nums) is even)

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Explores all game states recursively
Optimal	O(n)	O(1)	Uses XOR parity observation and game theory

Algorithm Walkthrough

1. Compute the XOR of every number in the array.

We iterate through the array and continuously XOR all values together. This gives the XOR of the entire board state. 2. Check whether the total XOR equals 0.

If the XOR is already 0 at the start of Alice's turn, the rules state that the current player wins immediately. Therefore Alice wins instantly. 3. If the XOR is not 0, check the array length parity.

If the number of elements is even, Alice can force a winning strategy.

If the number of elements is odd, Alice loses under optimal play. 4. Return the result.

The final condition is:

total_xor == 0 OR len(nums) % 2 == 0

Why it works

The core invariant is based on parity.

When the total XOR is non zero:

• Every legal move changes the XOR to another value.
• With an even number of elements, the first player can always maintain a favorable parity configuration.
• With an odd number of elements, the first player is eventually forced into the losing move.

A formal proof shows that when the XOR is non zero, the winning condition depends entirely on whether the remaining count of numbers is even or odd.

Therefore the game outcome is fully determined by:

• Whether the starting XOR is 0
• Whether the array length is even

Python Solution

from typing import List

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

        for num in nums:
            total_xor ^= num

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

The implementation is extremely compact because the mathematical observation eliminates the need for simulation.

First, we initialize total_xor to 0. We then iterate through every number and XOR it into the accumulator. By the end of the loop, total_xor contains the XOR of the entire array.

After computing the XOR, we evaluate the winning condition directly.

If total_xor == 0, Alice wins immediately according to the rules.

Otherwise, we check whether the array length is even. If it is even, Alice can force a win. If it is odd, she loses.

The solution uses constant extra space and only scans the array once.

Go Solution

func xorGame(nums []int) bool {
    totalXor := 0

    for _, num := range nums {
        totalXor ^= num
    }

    return totalXor == 0 || len(nums)%2 == 0
}

The Go implementation follows exactly the same logic as the Python version.

Go slices naturally handle empty and non empty collections, although this problem guarantees at least one element. Integer overflow is not a concern because XOR operations remain within integer bit widths and the input values are small.

The loop uses Go's range syntax to iterate through the slice efficiently.

Worked Examples

Example 1

Input: nums = [1,1,2]

First compute the total XOR.

Step	Value	Running XOR
Start	-	0
XOR 1	1	1
XOR 1	1	0
XOR 2	2	2

Final XOR:

2

Array length:

3

The XOR is non zero and the length is odd.

Therefore:

Alice loses

Return:

false

Example 2

Input: nums = [0,1]

Compute the XOR.

Step	Value	Running XOR
Start	-	0
XOR 0	0	0
XOR 1	1	1

Final XOR:

1

Array length:

2

The XOR is non zero, but the length is even.

Therefore Alice wins.

Return:

true

Example 3

Input: nums = [1,2,3]

Compute the XOR.

Step	Value	Running XOR
Start	-	0
XOR 1	1	1
XOR 2	2	3
XOR 3	3	0

Final XOR:

0

Because the XOR is already 0, Alice immediately wins according to the rules.

Return:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once to compute the XOR
Space	O(1)	Only a single accumulator variable is used

The runtime is linear because every element participates in exactly one XOR operation. No recursion, auxiliary arrays, or additional data structures are needed, so the extra memory usage remains constant.

Test Cases

from typing import List

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

        for num in nums:
            total_xor ^= num

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

solution = Solution()

assert solution.xorGame([1, 1, 2]) is False  # Example 1, odd length and nonzero XOR
assert solution.xorGame([0, 1]) is True      # Example 2, even length
assert solution.xorGame([1, 2, 3]) is True   # Example 3, XOR already zero

assert solution.xorGame([5]) is False        # Single nonzero element loses immediately
assert solution.xorGame([0]) is True         # Single zero element already has XOR zero

assert solution.xorGame([2, 2]) is True      # XOR zero and even length
assert solution.xorGame([4, 7]) is True      # Nonzero XOR but even length

assert solution.xorGame([1, 2, 4]) is False  # Odd length and nonzero XOR
assert solution.xorGame([7, 7, 7]) is False  # Odd length, XOR nonzero

assert solution.xorGame([8, 8, 3, 3]) is True   # XOR zero
assert solution.xorGame([1, 2, 3, 4]) is True   # Even length

assert solution.xorGame([0, 0, 0]) is True      # XOR zero with odd length
assert solution.xorGame([9, 9, 9, 9, 9]) is False  # Odd length and XOR nonzero

Test	Why
[1,1,2]	Validates odd length with nonzero XOR
[0,1]	Validates even length winning condition
[1,2,3]	Validates immediate win when XOR is zero
[5]	Smallest losing configuration
[0]	Smallest winning configuration
[2,2]	Confirms XOR cancellation
[4,7]	Confirms even length always wins
[1,2,4]	Another odd nonzero XOR losing case
[7,7,7]	Repeated values with odd count
[8,8,3,3]	Multiple XOR cancellations
[1,2,3,4]	Even length with arbitrary values
[0,0,0]	XOR zero despite odd size
[9,9,9,9,9]	Large repeated odd configuration

Edge Cases

One important edge case is when the array contains exactly one element. If that element is non zero, then the total XOR is non zero and the length is odd. Alice has only one possible move, removing the element, which leaves XOR 0 and causes her to lose immediately. The implementation handles this naturally through the parity and XOR conditions.

Another critical edge case occurs when the total XOR is already 0 before any move is made. According to the rules, the player whose turn starts with XOR 0 wins immediately. A naive simulation might incorrectly attempt to make moves first. The implementation explicitly checks total_xor == 0, ensuring this situation is handled correctly.

A third important edge case involves repeated values that cancel through XOR. For example:

[5,5,7,7]

has total XOR 0 because identical numbers cancel each other. A buggy implementation might focus only on array length or distinct values. The solution correctly computes the actual XOR of the entire array, so cancellation behavior is handled automatically.

Another subtle case is large arrays with arbitrary values. Since the optimal solution never simulates the game tree, performance remains efficient even for the maximum input size of 1000. The algorithm only requires a single pass through the array, making it both fast and memory efficient.