810. Chalkboard XOR Game #
Problem #
We are given non-negative integers nums[i] which are 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. (Also, we’ll say 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: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 becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.
Notes:
1 <= N <= 1000.0 <= nums[i] <= 2^16.
Problem Summary #
A non-negative integer array nums[i] is written on a chalkboard. Alice and Bob take turns erasing one number from the chalkboard, with Alice going first. If, after erasing a number, the bitwise XOR of all remaining numbers equals 0, the current player loses. (Also, if only one number remains, the bitwise XOR is that number itself; if no numbers remain, the bitwise XOR is 0.) Moreover, when it is a player’s turn, if the bitwise XOR of all numbers currently on the chalkboard equals 0, that player wins. Assuming both players make optimal moves at every step, return true if and only if Alice wins.
Solution Approach #
One situation where Alice is guaranteed to win is: Alice moves first, and the XOR result of all elements in the initial array is already 0. She automatically wins without needing to erase any number. Apart from this case, are there any others? Since the 2 players erase numbers alternately, and each time exactly one number is erased, for either of the two players, the parity of the number of remaining numbers on the chalkboard before each of their erasures must always be the same. Thus, parity becomes the breakthrough point.
If the length of nums is even, is Alice, the first player, guaranteed to lose? If she were guaranteed to lose, it would mean that no matter which number she erases, the XOR result of all remaining numbers would equal 0. Use proof by contradiction to show that the above conclusion is false. First, \( num[0] \oplus num[1] \oplus num[2] \oplus \cdots \oplus num[n-1] = X ≠ 0 \) , the initial XOR result of all elements is not 0. Suppose Alice currently erases the i-th element, 0 ≤ i < n. Let \(X_{n}\) represent the XOR result of the remaining elements after erasing the n-th element. According to the statement to be proved, no matter which number is erased, the XOR result of all remaining numbers equals 0. Therefore, \( X_{0} \oplus X_{1} \oplus X_{2} \oplus \cdots \oplus X_{n-1} = 0\) .
\[ \begin{aligned}0 &= X_{0} \oplus X_{1} \oplus X_{2} \oplus \cdots \oplus X_{n-1} \\0 &= (X \oplus nums[0]) \oplus (X \oplus nums[1]) \oplus (X \oplus nums[2]) \oplus \cdots \oplus (X \oplus nums[n-1])\\ 0 &= (X \oplus X \oplus \cdots \oplus X) \oplus (nums[0] \oplus nums[1] \oplus nums[2] \oplus \cdots \oplus nums[n-1])\\0 &= 0 \oplus X\\\\\Rightarrow X &= 0\\\end{aligned} \]Since n is even, the XOR result of n copies of X is 0. Eventually we derive X = 0, which clearly conflicts with the premise X ≠ 0. Therefore, the original proposition—that no matter which number is erased, the XOR result of all remaining numbers equals 0—is false. In other words, when n is even, it means that it is not the case that no matter which number is erased, the XOR result of all remaining numbers equals 0. That is, Alice has a winning strategy. Put another way, when the length of the array is even, the first player Alice can always find a number such that after erasing it, the XOR result of all remaining numbers is not 0.
In summary, there are 2 cases where Alice has a winning strategy:
- The XOR result of all elements in the initial array nums itself equals 0.
- The length of the array nums is even.
Code #
package leetcode
func xorGame(nums []int) bool {
if len(nums)%2 == 0 {
return true
}
xor := 0
for _, num := range nums {
xor ^= num
}
return xor == 0
}
中文