This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

The title

On the blackboard is written an array of non-negative integers nums[I]. Alice and Bob take turns to erase a number from the blackboard, Alice first. If after erasing a number, all remaining digits in bitwise xor result in 0, the current player loses the game. (Also, if there is only one number left, the bitwise xor operation yields itself; If there are no digits left, the bitwise xor operation results in 0.

In other words, when it’s a player’s turn, if all the numbers on the current board are xor equal to 0, that player wins.

Assuming that both players use the optimal solution at every step, return true if and only if Alice wins.

 

Example:

Nums = [1, 1, 2] output: false

Explanation: Alice has two choices: erase the number 1 or 2. If I erase the 1, the array becomes [1, 2]. The remaining digits are XOR by bit to get 1 XOR 2 = 3. So Bob can erase any number, because Alice will be the one to erase the last number, and she always loses. If Alice erases 2, then the array becomes [1, 1]. The remaining digits are XOR by bit to get 1 XOR 1 = 0. Alice will still lose the game.

Their thinking

Parity is constant

Because ALice and Bob take turns picking numbers, if ALice starts with an even number of elements, then ALice picks an even number of elements every time.

S^nums[i]=Si

Let Si be the xOR result of the array after removing the ith element, S be the xOR result of all elements, that is, Si^nums[I]=S, S^nums[I]=Si

Reduction to absurdity

When the array length is even and S! =0(because if S=0, then the winner is already decided), assuming that whatever element is taken, Si=0 is S0=0, S1=0……. Is equivalent to S0^S1^S2….. =0, substitute S^nums[I]=Si

(S^nums[0])^(S^nums[1])^.... = 0

(S^S...) ^(nums[0]^nums[1]....) = 0

And since S is xor for all elements, and the array length is even, there’s an even number of S’s, so

S^S… (odd number of S)=0, that is, S=0, and S! =0, so there is no Si=0, no matter which element is taken, that is to say, the side of the array with even length can make the other side never have any unique elements left or the result is 0.

So in order for Alice to win, there are only two scenarios

  • The xOR of the original array is 0, because Alice is first, so she wins
  • The length of the original array is even

code

class Solution {
    public boolean xorGame(int[] nums) {

        int res=0;
        if((nums.length&1) = =0) return true;
        for (int num : nums) {
            res^=num;
        }
        return res==0; }}Copy the code