Erase Until the XOR Is Zero
Numbers are written on a board. Two players take turns, and a turn erases exactly one number. The game follows two rules:
- If the XOR of all the numbers on the board is 0 at the start of a player's turn, that player wins at once.
- A player whose move leaves a board with XOR 0 loses at once. The XOR of an empty board is 0, so erasing the last number loses.
Both players play as well as possible. Return True if the player who moves first wins, otherwise False.
Example 1
nums [3,5,6]
returns true
3 ^ 5 ^ 6 is 0 before the first move, so the first player wins on the spot.
Example 2
nums [4,9]
returns true
The first player erases either number. The second player must then erase the last number and loses.
Example 3
nums [1,2,4]
returns false
Whatever is erased first, two different numbers stay. The second player erases one, and the first player is left with the last number.
Constraints
1 <= len(nums) <= 3000 <= nums[i] < 2**16
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.