Watch 8 video solutions for Chalkboard XOR Game, a hard level problem involving Array, Math, Bit Manipulation. This walkthrough by SDE Skills has 795 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 10000 <= nums[i] < 216Problem Overview: You are given an array of integers written on a chalkboard. Two players take turns erasing one number. If the XOR of the remaining numbers becomes 0 immediately after a move, the player who made that move loses. Both players play optimally. The task is to determine whether Alice (the first player) can guarantee a win.
Approach 1: Mathematical Insight (O(n) time, O(1) space)
The key observation comes from properties of XOR and optimal play in game theory. Compute the XOR of all elements in the array. If the XOR is already 0, Alice wins immediately because any move she makes forces Bob into a losing configuration. If the XOR is non-zero, the parity of the array length becomes critical. When the number of elements is even, Alice can always remove a number while keeping the total XOR non-zero, forcing Bob into the dangerous state. When the array length is odd and the XOR is non-zero, every possible move risks leaving a zero XOR for the opponent to exploit. The algorithm simply computes the total XOR using a single pass through the array and checks the array length parity. This approach leverages properties of bit manipulation and avoids exploring game states entirely.
Approach 2: Dynamic Programming (State Exploration) (O(n * 2^n) time, O(2^n) space)
A more direct way to reason about the game is to simulate all possible states. Represent the remaining numbers as a bitmask where each bit indicates whether a number is still on the board. For each state, compute the XOR of active elements and try removing each available number. If any removal leads to a state where the opponent loses, the current state is winning. Memoization stores results for each mask to avoid recomputation. This turns the exponential search tree into a manageable DP over subsets. The approach clearly models the game mechanics but becomes expensive as n grows because the state space contains 2^n subsets. It demonstrates how brute-force game analysis works before discovering the mathematical shortcut.
Recommended for interviews: The mathematical insight approach is what interviewers typically expect. It reduces the entire game to two quick checks: compute the XOR of all numbers and inspect whether the array length is even. Explaining the DP or recursive game simulation first can show your reasoning process, but recognizing the XOR parity pattern demonstrates strong understanding of mathematical reasoning and competitive programming tricks.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mathematical Insight | O(n) | O(1) | Optimal solution for interviews and production; relies on XOR parity observation |
| Dynamic Programming (State Mask) | O(n * 2^n) | O(2^n) | Useful for understanding the game mechanics or validating the mathematical insight |