Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/810.html

810. Chalkboard XOR Game

Level

Hard

Description

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.

Solution

If the bitwise XOR of all the elements in nums equals 0, then Alice will win the game. Otherwise, suppose the game continues until all the integers are erased. If there are even number of integers initially, then Alice will win the game. If there are odd number of integers initially, then Bob will win the game.

Is it possible that there are even number of integers initially and Alice will lose? The answer is no. Suppose at some point it is Alice’s turn with n integers on the chalkboard, where n is even. Alice will lose only if both of the following conditions are met.

  1. The bitwise XOR of all n integers does not equal 0. That is, X = x1 ^ x2 ^ x3 ^ … xn != 0, where x1 to xn are the n integers on the chalkboard.
  2. After erasing any one number on the chalkboard, the bitwise XOR of the remaining n - 1 integers equals 0. That is, X ^ xk == 0 for any 1 <= k <= n.

Since 0 ^ 0 == 0, it can be obtained that (X ^ x1) ^ (X ^ x2) ^ (X ^ x3) ^ … ^ (X ^ xn) = 0.

However, the following result can also be obtained. In the following, Xk == X for all 1 <= k <= n. The subscripts for X are added only for showing how many numbers are calculated in bitwise XOR. Note that n is even.

(X ^ x1) ^ (X ^ x2) ^ (X ^ x3) ^ … ^ (X ^ xn) = (X1 ^ X2 ^ X3 ^ … ^ Xn) ^ (x1 ^ x2 ^ x3 ^ … ^ xn) = 0 ^ X.

Therefore, it can be seen that (X ^ x1) ^ (X ^ x2) ^ (X ^ x3) ^ … ^ (X ^ xn) = 0 and (X ^ x1) ^ (X ^ x2) ^ (X ^ x3) ^ … ^ (X ^ xn) = 0 ^ X are both true, so 0 ^ X = 0, which contradicts with the fact that X != 0.

Therefore, Alice always have a choice that will not make the bitwise OR of the remaining elements on the chlakboard equals 0. So if Alice starts with even number of integers on the chalkboard, then Alice will always win. If Alice starts with odd number of integers on the chalkboard and Alice does not win initially, then Alice has to erase one integer, which leaves even number of integers to Bob, so Bob will win the game.

So the solution to the problem is quite straightforward. Alice will win the game if and only if one of the following conditions are met.

  1. The length of nums is even.
  2. The bitwise XOR of all the elements in nums is 0.
  • class Solution {
    public boolean xorGame(int[] nums) {
        if (nums.length % 2 == 0)
            return true;
        int xor = 0;
        for (int num : nums)
            xor ^= num;
        return xor == 0;
    }
}

  • // OJ: https://leetcode.com/problems/chalkboard-xor-game/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool xorGame(vector<int>& A) {
        int x = 0;
        for (int n : A) x ^= n;
        return A.size() % 2 == 0 || x == 0;
    }
};

  • class Solution:
    def xorGame(self, nums: List[int]) -> bool:
        return len(nums) % 2 == 0 or reduce(xor, nums) == 0



  • func xorGame(nums []int) bool {
	if len(nums)%2 == 0 {
		return true
	}
	x := 0
	for _, v := range nums {
		x ^= v
	}
	return x == 0
}

All Problems

All Solutions