#810
Chalkboard XOR Game
expert · 1125 · lc hard +32 · verified · 65.9% accepted · 246 likes · top 71%
Description
You are given an array of integers nums representing numbers written on a chalkboard.
Alice and Bob alternate erasing one number per turn, with Alice going first. If erasing a number makes the XOR of all remaining numbers equal 0, the player who erased it loses. The XOR of a single element is the element itself; the XOR of no elements is 0.
Additionally, if a player's turn begins when the XOR of all remaining numbers is already 0, that player wins immediately.
Return true if Alice wins under optimal play by both players, otherwise return false.
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
Code
1
2
3