810. Chalkboard XOR Game

HardBit ManipulationBrainteaserArrayMathGame Theory

Problem Description

In this problem, we have a game based on numbers written on a chalkboard represented by an array of integers nums. There are two players, Alice and Bob, who take turns erasing exactly one number from the chalkboard. Alice always goes first. The goal is to avoid making the bitwise XOR of all elements on the chalkboard equal to 0. If a player erases a number and the XOR turns to 0, that player loses. Bitwise XOR of one element is the element itself, while the bitwise XOR of no elements is 0.

Additionally, there is a win condition right at the start of a player's turn. If the bitwise XOR of all elements before the player takes an action is 0, then that player immediately wins the game.

The task is to return true if Alice wins the game when both players play optimally, otherwise false.

Intuition

To solve this problem, we need to analyze the conditions under which a player can win, keeping in mind that both Alice and Bob play optimally (they make the best possible moves).

Firstly, one straightforward condition is if the initial XOR of all numbers is 0. If Alice begins and the XOR is 0, she wins without making a move.

Secondly, consider the condition regarding the count of numbers on the chalkboard. If the count is even, Alice can always mirror Bob's moves. Whenever Bob erases a number to avoid losing, Alice can do the same. Since the count began even and decreases by two with each full round (Alice and Bob each erase one), Alice will never be forced into a losing move because she will always respond to Bob’s moves and the number of elements will stay even on her turn.

The optimal strategy for both players is to always erase a number that keeps the xor sum non-zero if possible. If not, the player losing is the one forced to make the xor sum 0. Hence, Alice will only lose if she starts with an odd number of elements on the chalkboard and cannot make the XOR sum 0 on her first move.

Learn more about Math patterns.

Solution Approach

The solution approach utilizes a Python function xorGame, which determines the winner of the game using two simple checks based on the rules of the game as described in the problem description.

To implement the solution, we use two Python features:

The reduce function from the functools module.
The xor function from the operator module.

Here is how the solution approach works in terms of these components and logic:

The xor function is a binary operation that performs bit-by-bit exclusive OR on two integers. It is used in conjunction with reduce to calculate the cumulative XOR of all elements in the nums list.
reduce(function, sequence) applies the function cumulatively to the items of the sequence, from left to right, so as to reduce the sequence to a single value. For example, reduce(xor, nums) applies the xor function to the elements of nums and gives a single integer result, which is the XOR of all numbers.
The solution then relies on two conditions:
- len(nums) % 2 == 0: As stated in the intuition, if the number of elements in nums is even, Alice can always ensure she won't be the one to cause the XOR sum to become 0. She can do this by mirroring Bob's moves. Therefore, if the length of the list nums is even, the function returns true indicating Alice wins.
- reduce(xor, nums) == 0: This condition checks if the initial XOR of all elements is 0. If it is, Alice wins by the game's rules without having to erase any number, so the function returns true.

The xorGame function in Python combines these checks with the or operator. If either condition is true, Alice wins the game; otherwise, Bob does.

Here’s the implementation distilled into its logic:

Check if the length of nums is even; if so, return true and Alice wins.
Calculate the XOR of all elements in nums; if it's 0, return true and Alice wins.
If both checks fail, return false, indicating Bob wins.

This implementation is short and efficient. It directly applies mathematical properties of the XOR operation and parity checks (even or odd number of elements) in determining the winner of the game.

The provided implementation also assumes optimal play from both participants, meaning they will both do their best to avoid losing. Considering this, the checks cover all scenarios for Alice to win.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach described above. Suppose we have the following array of integers, which represents the numbers on the chalkboard: nums = [1, 1, 2].

Now, let's walk through the logic:

First, we count the number of elements in nums. There are three elements, so the count is odd. This means that we can't immediately decide Alice wins based on the even-count condition.
Next, we calculate the XOR of all elements: 1 XOR 1 XOR 2. In binary, this is 01 XOR 01 XOR 10. The XOR of the first two 1s cancels each other out, leaving us with 0 XOR 2, which equals 2. The result is non-zero, so we now know that the game will not be decided by the initial XOR being 0.

Because both conditions for Alice to win (an even number of elements and an initial XOR of 0) are not met, the solution approach will return false. This indicates that, under optimal play, Bob will have the winning strategy in this scenario.

Solution Implementation

1from functools import reduce
2from operator import xor
3from typing import List
4
5class Solution:
6    def xor_game(self, nums: List[int]) -> bool:
7        # The xor game can be won in two scenarios:
8        # 1. If the length of the list nums is even, the player starting can always win
9        # by pairing up the numbers and xoring each pair.
10        if len(nums) % 2 == 0:
11            return True
12        # 2. If the xor of all numbers in the list nums is 0, the player can also win,
13        # because no matter how the other player picks a number, the first player can
14        # always choose a number that will reset the xor back to 0.
15        else:
16            # reduce applies the xor operator cumulatively to the items of nums,
17            # from left to right, so as to reduce the iterable nums to a single value.
18            return reduce(xor, nums) == 0
19
20# Example usage:
21# sol = Solution()
22# print(sol.xor_game([1, 1, 2]))  # Outputs: True, because len(nums) is odd but xor of all numbers is 0
23

1class Solution {
2  
3    // Method to check if the XOR game can be won.
4    public boolean xorGame(int[] nums) {
5        // Check for two conditions:
6        // 1. If the length of the array is even, the player starting the game can always win.
7        // 2. If the XOR of all elements in the array is 0, the player can also win.
8        return isEvenLength(nums) || isXorZero(nums);
9    }
10  
11    // Helper method to check if the length of the array is even.
12    private boolean isEvenLength(int[] nums) {
13        return nums.length % 2 == 0;
14    }
15  
16    // Helper method to calculate the XOR of all elements in the array and check if it is 0.
17    private boolean isXorZero(int[] nums) {
18        int xorResult = Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
19        return xorResult == 0;
20    }
21}
22

1#include <vector> // Include the necessary header for vector
2
3class Solution {
4public:
5    // Function to determine if the player starting the XOR game will always win
6    bool xorGame(const std::vector<int>& nums) {
7        // If there's an even number of elements, the first player will always win
8        if (nums.size() % 2 == 0) {
9            return true;
10        }
11      
12        // Calculate the XOR of all elements in the vector
13        int xorSum = 0;
14        for (int num : nums) {
15            xorSum ^= num;
16        }
17      
18        // The first player also wins if the XOR sum of all numbers is 0
19        return xorSum == 0;
20    }
21};
22

1// Function to determine if the player starting the XOR game will always win
2function xorGame(nums: number[]): boolean {
3    // If there's an even number of elements, the first player will always win
4    if (nums.length % 2 === 0) {
5        return true;
6    }
7  
8    // Calculate the XOR of all elements in the array
9    let xorSum: number = 0;
10    for (let num of nums) {
11        xorSum ^= num;
12    }
13  
14    // The first player also wins if the XOR sum of all numbers is 0
15    return xorSum === 0;
16}
17

Time and Space Complexity

The time complexity of the function xorGame is O(N), where N is the number of elements in the list nums. This is because the function computes the xor of all the elements in the list using the reduce function along with the xor operator, which takes linear time.

The space complexity of the function is O(1). No additional space is used proportional to the size of the input, as the xor operation is done in-place and the comparison with zero also uses constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don’t know