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.
The game can be reduced to a theoretical observation: Alice will win if the XOR of all elements of the array (before any move) is already 0 or if the length of the array is even. This is because, under optimal play, a XOR of 0 or an even number of moves ensures Alice's win. When it's an even number, Bob will be the one forced to make a move that reduces the XOR to 0 if possible.
The solution checks if the XOR of the entire list is already zero or if the list length is even. If either condition is met, Alice wins. We use Python's reduce function to calculate the XOR of the nums list.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as no extra space is used beyond a few variables.
This approach builds upon understanding the subproblems of removing each number and calculating the XOR of the remaining elements. Even though its complexity is higher, this method helps us understand more granular moves and outcomes if not assuming mathematical shortcuts.
The dynamic programming approach uses recursion with memoization to explore different outcomes of removing each number from nums. If removing any number of remaining results in a lose state (`xorSum` becomes zero), the current player loses.
Python
C++
Java
C#
JavaScript
Time Complexity: O(2^n) due to the exponential number of XOR states possible.
Space Complexity: O(n), largely dictated by function call stack depth.
According to the game rules, if the XOR result of all numbers on the blackboard is 0 when it is a player's turn, that player wins. Since Alice goes first, if the XOR result of all numbers in nums is 0, Alice can win.
When the XOR result of all numbers in nums is not 0, let's analyze Alice's winning situation based on the parity of the length of the array nums.
When the length of nums is even, if Alice is destined to lose, there is only one situation: no matter which number Alice erases, the XOR result of all remaining numbers equals 0. Let's analyze whether this situation exists.
Assume the length of the array nums is n, and n is even. Let the XOR result of all numbers be S, then:
$
S = nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1] neq 0
Let S_i be the XOR result after erasing the i-th number from the array nums, then:
S_i \oplus nums[i] = S
XOR both sides of the equation by nums[i], we get:
S_i = S \oplus nums[i]
If no matter which number Alice erases, the XOR result of all remaining numbers equals 0, then for all i, we have S_i = 0, i.e.,
S_0 \oplus S_1 \oplus cdots \oplus S_{n-1} = 0
Substitute S_i = S \oplus nums[i] into the above equation, we get:
S \oplus nums[0] \oplus S \oplus nums[1] \oplus cdots \oplus S \oplus nums[n-1] = 0
There are n (even) S terms in the above equation, and nums[0] \oplus nums[1] \oplus cdots \oplus nums[n-1] also equals S, so the equation is equivalent to 0 \oplus S = 0. This contradicts S neq 0, so this situation does not exist. Therefore, when the length of nums is even, Alice is guaranteed to win.
If the length is odd, then after Alice erases a number, the remaining numbers are even in length, leaving Bob with an even-length situation, which means Bob is guaranteed to win, and thus Alice is destined to lose.
In conclusion, Alice can win when the length of nums is even or the XOR result of all numbers in nums is 0.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.
| Approach | Complexity |
|---|---|
| Approach 1: Mathematical Insight | Time Complexity: O(n), where n is the length of nums. |
| Approach 2: Dynamic Programming | Time Complexity: O(2^n) due to the exponential number of XOR states possible. |
| Bit Manipulation | — |
| 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 |
Leetcode [810] Chalkboard XOR Game • SDE Skills • 795 views views
Watch 7 more video solutions →Practice Chalkboard XOR Game with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor