# Chalkboard XOR Game
**Difficulty:** HARD
[External](https://leetcode.com/problems/chalkboard-xor-game)
Canonical: https://scaleengineer.com/dsa/problems/chalkboard-xor-game
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** Array
**Companies:** [HashedIn](https://scaleengineer.com/companies/hashedin)
---
## 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] < 216`

# Approaches
## Brute-Force with Memoization (Game State Simulation)
A standard approach for solving game theory problems is to model the game as a state graph and use recursion with memoization (a form of dynamic programming) to determine the outcome. A state is defined by the numbers currently on the chalkboard. The function `canWin` determines if the current player can win from a given state. We explore all possible moves from the current state. If any move leads to a state where the opponent is guaranteed to lose, the current player has a winning strategy. Memoization is crucial to cache the results for already-visited states, pruning the search space, but the number of states is still prohibitively large.
**Time:** O(N^2 * 2^N). There are `2^N` possible subsets (states). For each state, we iterate through up to `N` numbers. Creating the new list for the recursive call takes O(N). This makes the complexity for each state O(N^2), leading to an overall exponential time complexity. · **Space:** O(N * 2^N), where N is the number of elements. The memoization table can store up to `2^N` states, and each state (the list of numbers) can take up to O(N) space.
**Pros:** It's a general and intuitive method for solving impartial games.; It correctly models the game logic and rules.
**Cons:** The number of possible subsets of `nums` is `2^N`, leading to an exponential number of states.; The time and space complexity are too high for the given constraints (`N <= 1000`), resulting in a 'Time Limit Exceeded' or 'Memory Limit Exceeded' error.
### Explanation
This approach simulates the game turn by turn. We define a function `canWin` which takes the current list of numbers on the chalkboard. To avoid re-calculating the result for the same set of numbers, we use a map for memoization, where the key represents the state (the list of numbers) and the value is the boolean result.

The logic inside `canWin` is as follows:
- First, check if the result for the current state is already in our memoization table. If so, return the cached value.
- Calculate the XOR sum of the current numbers. If it's 0, the current player wins by the game's rules. We store `true` and return it.
- If the XOR sum is not 0, the player must make a move. A move is picking a number `num` to erase. The player loses if this move makes the new XOR sum 0. So, a player must pick a `num` such that `current_xor_sum ^ num != 0`.
- We iterate through all possible valid moves. For each move, we check if the opponent can win from the resulting state by making a recursive call. If we find any move for which the opponent *cannot* win (the recursive call returns `false`), it means we have found a winning line of play. We can then cache and return `true`.
- If we iterate through all valid moves and find that the opponent always has a winning response, then the current player will lose from this state. We cache and return `false`.

```java
import java.util.*;

class Solution {
    public boolean xorGame(int[] nums) {
        List<Integer> initialNums = new ArrayList<>();
        for (int num : nums) {
            initialNums.add(num);
        }
        // Sorting is important for consistent map keys if lists are used directly
        // A better key would be a canonical string representation.
        Collections.sort(initialNums);
        return canWin(initialNums, new HashMap<>());
    }

    private boolean canWin(List<Integer> nums, Map<List<Integer>, Boolean> memo) {
        if (nums.isEmpty()) {
            return false; // XOR sum is 0, previous player lost, so current player wins.
                          // This case is handled by the xorSum == 0 check.
        }

        if (memo.containsKey(nums)) {
            return memo.get(nums);
        }

        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }

        if (xorSum == 0) {
            memo.put(nums, true);
            return true;
        }

        // Try all possible moves
        for (int i = 0; i < nums.size(); i++) {
            int numToRemove = nums.get(i);
            
            // A player loses if their move makes the XOR sum 0.
            // So, a player must make a move that does NOT result in 0.
            if ((xorSum ^ numToRemove) != 0) {
                List<Integer> nextNums = new ArrayList<>(nums);
                nextNums.remove(i);
                
                // If the opponent cannot win from the next state, we win.
                if (!canWin(nextNums, memo)) {
                    memo.put(nums, true);
                    return true;
                }
            }
        }

        // If all moves lead to a state where the opponent wins, we lose.
        memo.put(nums, false);
        return false;
    }
}
```
Note: The above code is conceptually correct but will be too slow for the given constraints. Using a sorted list as a map key is also inefficient.
### Algorithm
1. Define a recursive function, say `canWin(currentNums, memo)`, that returns `true` if the current player can win from the state defined by `currentNums`.
2. The state can be uniquely identified by the list of numbers. To use it as a key in a memoization map, we can sort the list and convert it to a string or use the list object itself (if its `hashCode` and `equals` methods are handled correctly).
3. **Base Case/Winning Condition:** Calculate the bitwise XOR sum `X` of all numbers in `currentNums`. If `X == 0`, the current player wins immediately. Return `true`.
4. **Recursive Step:** The current player needs to find a move that leads to a state from which the opponent cannot win.
5. Iterate through each number `num` in `currentNums`.
6. A move consists of removing `num`. This move is a losing move for the current player if the new XOR sum becomes 0. The new XOR sum is `X ^ num`. So, the player must choose a `num` such that `X ^ num != 0`.
7. For each such valid move, create the next state `nextNums = currentNums - {num}`.
8. Recursively call `canWin(nextNums, memo)`. If this call returns `false`, it means we found a move where the opponent loses. Therefore, the current player wins. We can return `true`.
9. If after trying all valid moves, none lead to a state where the opponent loses (i.e., all recursive calls return `true`), then the current player has no winning move and will lose. Return `false`.
10. Before returning, store the result in the memoization table to avoid recomputing for the same state.

## Optimal Solution using Game Theory and XOR Properties
Instead of simulating the game, we can analyze its mathematical properties to find a direct solution. This is a common theme in combinatorial game theory. The winner of the game can be determined by two simple properties of the initial state: the bitwise XOR sum of all numbers and the parity (even or odd) of the number of elements. By analyzing the winning and losing conditions, we can deduce a simple rule that predicts the winner without exploring the game tree at all.
**Time:** O(N), where N is the length of the `nums` array. We need to iterate through the array once to calculate the bitwise XOR sum. · **Space:** O(1). We only use a single integer variable to store the running XOR sum.
**Pros:** Extremely efficient with linear time complexity.; Requires constant extra space.; Provides a complete solution that passes all constraints.
**Cons:** The solution is not immediately obvious and requires a deep understanding of the game's properties and bitwise XOR.
### Explanation
Let's analyze the game rules to find a winning strategy.

**Winning/Losing Conditions:**
1.  A player wins if, at the start of their turn, the XOR sum of all numbers on the board is `0`.
2.  A player loses if they make a move (erase a number `num`) that causes the XOR sum of the remaining numbers to become `0`.

Let `X` be the XOR sum of the numbers on the board at the start of a player's turn.

**Case 1: Initial XOR sum is 0.**
If the XOR sum of the initial `nums` array is `0`, Alice starts her turn and wins immediately. So, if `X_initial == 0`, Alice wins.

**Case 2: Initial XOR sum is not 0.**
Alice must make a move. Let the current XOR sum be `X` and the number of elements be `n`. Alice must choose a number `num` to erase. The new XOR sum will be `X ^ num`. To not lose, she must choose `num` such that `X ^ num != 0`, which means `num != X`.

**Can a player always make a non-losing move?**
A player is forced to lose if, for every number `num_i` on the board, `num_i = X`. Let's see when this can happen.
If all `n` numbers on the board are equal to `X`, their total XOR sum is `X ^ X ^ ... ^ X` (`n` times).
- If `n` is even, this sum is `0`. This contradicts our assumption that `X != 0`.
- If `n` is odd, this sum is `X`. This is consistent.

This means a player can only be forced into a losing position if they face a board with an **odd** number of elements.
If a player faces a board with an **even** number of elements and a non-zero XOR sum, it's impossible for all numbers to be equal to the XOR sum. Thus, there must be at least one number `num` such that `num != X`. The player can safely remove this `num` and pass the turn.

**Applying this to Alice and Bob:**
- **If `nums.length` is even:** Alice starts with an even number of elements. Since the initial XOR sum is not 0, she can always make a non-losing move. After her move, the board will have an odd number of elements for Bob. Bob will then make a move, leaving an even number for Alice. This continues. Alice always plays on a board with an even number of elements, and Bob on a board with an odd number. Since Alice can never be forced to lose, she will continue playing until the board is small. Eventually, Bob will face a board with 1 element. He must remove it, making the XOR sum 0, and he will lose. Thus, if `N` is even, Alice wins.

- **If `nums.length` is odd:** Alice starts with an odd number of elements. She might be forced to lose on her first move (e.g., `[7,7,7]`). Even if she can make a non-losing move, she will leave a board with an even number of elements for Bob. Now, Bob is in the winning position described above. Bob has a strategy to never lose, so Alice will eventually lose. Thus, if `N` is odd, Alice loses.

**Conclusion:**
Alice wins if `initial_xor_sum == 0` OR `nums.length % 2 == 0`.

```java
class Solution {
    public boolean xorGame(int[] nums) {
        int xorSum = 0;
        for (int num : nums) {
            xorSum ^= num;
        }

        // Alice wins if the initial XOR sum is 0.
        if (xorSum == 0) {
            return true;
        }

        // If the XOR sum is not 0, the game depends on the number of elements.
        // If N is even, Alice can always make a move such that the XOR sum
        // of the remaining elements is not 0. Bob will be left in a state
        // with an odd number of elements. Eventually, Bob will be forced to lose.
        // If N is odd, Alice makes a move and leaves Bob with an even number of
        // elements, putting Bob in a winning position.
        return nums.length % 2 == 0;
    }
}
```
### Algorithm
1. Calculate the bitwise XOR sum of all elements in the `nums` array.
2. Get the total number of elements, `N`, from the length of the array.
3. Apply the winning condition logic:
   - If the initial XOR sum is `0`, Alice wins immediately on her first turn.
   - If the initial XOR sum is not `0`, the outcome depends on the number of elements `N`.
   - If `N` is even, Alice is guaranteed to win.
   - If `N` is odd, Alice will lose (assuming optimal play from Bob).
4. Return `true` if `xor_sum == 0` or `N % 2 == 0`, and `false` otherwise.

# Solutions
### Java

```java
class Solution {
public
  boolean xorGame(int[] nums) {
    return nums.length % 2 == 0 ||
           Arrays.stream(nums).reduce(0, (a, b)->a ^ b) == 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool xorGame(vector<int> &nums) {
    if (nums.size() % 2 == 0)
      return true;
    int x = 0;
    for (int &v : nums)
      x ^= v;
    return x == 0;
  }
};

```

### Python

```python
class Solution:
    def xorGame(
        self, nums: List[int]) -> bool: return len(nums) % 2 == 0 or reduce(xor, nums) == 0

```