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] < 216The 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.
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.
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.
| 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. |
How to EASILY solve LeetCode problems • NeetCode • 427,694 views views
Watch 9 more video solutions →Practice Chalkboard XOR Game with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor