Problem

You are given an array of integers nums represents the numbers 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. 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.

Examples

Example 1

1
2
3
4
5
6

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

1
2

Input: nums = [0,1]
Output: true

Example 3

1
2

Input: nums = [1,2,3]
Output: true

Constraints

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] < 216

Solution

Method 1 – Game Theory and XOR Parity

Intuition: The game is a variant of Nim. If the XOR of all numbers is 0 at the start, Alice wins immediately. Otherwise, if the number of elements is even, Alice can always win by mirroring Bob’s moves. If the number of elements is odd and the XOR is not 0, Alice cannot win if both play optimally.

Approach:

  1. Compute the XOR of all elements in nums.
  2. If the XOR is 0, Alice wins (return true).
  3. If the length of nums is even, Alice wins (return true).
  4. Otherwise, Alice loses (return false).

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        int x = 0;
        for (int n : nums) x ^= n;
        return x == 0 || nums.size() % 2 == 0;
    }
};
1
2
3
4
5
6
7

func xorGame(nums []int) bool {
    x := 0
    for _, n := range nums {
        x ^= n
    }
    return x == 0 || len(nums)%2 == 0
}
1
2
3
4
5
6
7

class Solution {
    public boolean xorGame(int[] nums) {
        int x = 0;
        for (int n : nums) x ^= n;
        return x == 0 || nums.length % 2 == 0;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun xorGame(nums: IntArray): Boolean {
        var x = 0
        for (n in nums) x = x xor n
        return x == 0 || nums.size % 2 == 0
    }
}
1
2
3
4
5
6

class Solution:
    def xorGame(self, nums: list[int]) -> bool:
        x = 0
        for n in nums:
            x ^= n
        return x == 0 or len(nums) % 2 == 0
1
2
3
4
5
6

impl Solution {
    pub fn xor_game(nums: Vec<i32>) -> bool {
        let x = nums.iter().fold(0, |acc, &n| acc ^ n);
        x == 0 || nums.len() % 2 == 0
    }
}

Complexity

  • ⏰ Time complexity: O(N)
  • 🧺 Space complexity: O(1)