810. Chalkboard XOR Game
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 thefunctools
module. - The
xor
function from theoperator
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 withreduce
to calculate the cumulative XOR of all elements in thenums
list. reduce(function, sequence)
applies thefunction
cumulatively to the items of thesequence
, from left to right, so as to reduce the sequence to a single value. For example,reduce(xor, nums)
applies thexor
function to the elements ofnums
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 innums
is even, Alice can always ensure she won't be the one to cause the XOR sum to become0
. She can do this by mirroring Bob's moves. Therefore, if the length of the listnums
is even, the function returnstrue
indicating Alice wins.reduce(xor, nums) == 0
: This condition checks if the initial XOR of all elements is0
. If it is, Alice wins by the game's rules without having to erase any number, so the function returnstrue
.
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, returntrue
and Alice wins. - Calculate the XOR of all elements in
nums
; if it's0
, returntrue
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 EvaluatorExample 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 is01 XOR 01 XOR 10
. The XOR of the first two1s
cancels each other out, leaving us with0 XOR 2
, which equals2
. The result is non-zero, so we now know that the game will not be decided by the initial XOR being0
.
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.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!