# 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

| Item | Meaning |
|---|---|
| Input | An array `nums` of non-negative integers |
| Output | `True` if Alice wins, otherwise `False` |
| Move | Erase exactly one number |
| Losing condition | A player loses if their move makes the remaining XOR equal `0` |
| Immediate win | A player wins if their turn starts with XOR already equal `0` |

## Examples

Example 1:

```python
nums = [1, 1, 2]
```

The total XOR is:

```python
1 ^ 1 ^ 2 = 2
```

Alice has two meaningful choices.

If Alice erases `2`, the remaining numbers are:

```python
[1, 1]
```

Their XOR is:

```python
1 ^ 1 = 0
```

So Alice loses immediately.

If Alice erases `1`, the remaining numbers are:

```python
[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:

```python
False
```

Example 2:

```python
nums = [0, 1]
```

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

The answer is:

```python
True
```

Example 3:

```python
nums = [1, 2, 3]
```

The total XOR is:

```python
1 ^ 2 ^ 3 = 0
```

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

The answer is:

```python
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:

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

There are two simple winning cases for Alice:

```python
x == 0
```

or:

```python
len(nums) % 2 == 0
```

So the final answer is:

```python
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:

```python
x ^ nums[i]
```

For that to be `0`, we would need:

```python
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:

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

Then return:

```python
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)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We XOR every number once |
| Space | `O(1)` | We store only the running XOR |

## Implementation

```python
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:

```python
total = 0
```

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

We update it with every number:

```python
for num in nums:
    total ^= num
```

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

Then we apply the theorem:

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `[1, 1, 2]` | Official losing example |
| `[0, 1]` | Even length wins |
| `[1, 2, 3]` | Initial XOR is `0` |
| `[1]` | Odd length and non-zero XOR loses |
| `[0]` | Initial XOR is `0` |
| `[5, 5]` | Initial XOR is `0` and length is even |