Chalkboard Xor Game In C++

In this tutorial, we will explore the Chalkboard XIR Game implemented in the C++ programming language.

Problem Statement:

This scenario pertains to a game where participants take turns eliminating numbers from a chalkboard using an array of integers known as countnums. Radha and Bob engage in this activity, removing one number at a time in a sequential manner. Radha initiates the game. The primary goal is to avoid having all elements in countnums result in a bitwise XOR equal to 0. If a player selects a number that causes the XOR to become 0, they are defeated. An element represents the result of a bitwise XOR operation with a single element, while 0 signifies the outcome of XOR with no elements.

At the start of a player's turn, there is an additional condition for winning. The player achieves an instant victory if the result of performing a bitwise XOR operation on all elements equals 0 prior to making any moves. If Radha emerges victorious in a scenario where both players strategize optimally, the function will output true; otherwise, it will output false.

Solution Approach:

When it comes to these components and reasoning, the approach plan operates in the following manner:

By utilizing two numerical values, the XOR operation conducts exclusive OR comparisons on a bit-by-bit basis within a binary context. When combined with the reduce function, it calculates the collective XOR outcome for every item within the countnums collection.

The reduce(function, sequence) method iterates through the sequence, applying the function from left to right to reduce it to a single value. In this case, the reduce function performs XOR operation on the numbers in the sequence, resulting in an integer that is the XOR of all elements within the countnums array.

The resolution depends on two factors:

• ✅ len(nums) % 2 == 0: Radha may always make sure that she won't be the one to make the XOR sum go to zero if the number of elements in countnums is even .
• ✅ She can accomplish this by imitating Bob's actions.
• ✅ Thus, the function returns true , which means that Radha wins , if the list's length, countnums , is even .
• ✅ reduce(nums, xor) == 0: This condition determines if the first XOR of every element is 0.
• ✅ The method returns true because Radha wins according to the game's rules without remRadha having any numbers.

It is the implementation reduced to its most basic form:

• ✅ Verify that the number length is even . If it is, return true, and Radha wins.
• ✅ Determine the XOR of every element in countnums ; if the result is 0 , return true, and then Alice is the winner.
• ✅ If both checks are unsuccessful, it returns false , signifying Bob's victory.

Example:

Let's look at a brief example to demonstrate the above-discussed solution approach:-

• ✅ Assume the numbers on the whiteboard are represented by the array of integers below: nums is [3, 2, 3].
• ✅ We start by counting the elements in countnums . The number is odd because there are three elements.
• ✅ It implies that the even-count criterion does not allow us to declare Radha the winner right now.
• ✅ The XOR of every element is determined as follows: 1 XOR 1 XOR 2 .
• ✅ This is 01 XOR 01 XOR 10 in binary. The initial two 1s cancel each other out via XOR, giving us 0 XOR 2, equal to 2.
• ✅ As the outcome is non-zero, we can conclude that the starting XOR of 0 will not determine the outcome of the game.
• ✅ The solution technique will conclude that Radha will not win since the two conditions necessary for her victory - an even number of components and an initial XOR of 0 - are not satisfied.
• ✅ It implies that Bob will have a winning strategy in this case if all goes according to plan,

C++ Code:

#include <iostream>
#include <vector>
#include <numeric> // for std::accumulate
using namespace std;
int xorOperation(const vector<int>& nums) {
    // XOR operation on all elements of nums
    return accumulate(nums.begin(), nums.end(), 0, [](int a, int b) { return a ^ b; });
}
bool xorGame(const vector<int>& nums) {
    if (nums.size() % 2 == 0) {
        return true;  // Radha wins if the number of elements is even
    }
    if (xorOperation(nums) == 0) {
        return true;  // Radha wins if the initial XOR of all elements is 0
    }
    return false;  // Bob wins otherwise
}
int main() {
    // Example usage:
    vector<int> nums = {3, 2, 3};
    if (xorGame(nums)) {
        cout << "Radha wins!" << endl;
    } else {
        cout << "Bob wins!" << endl;
    }
    return 0;
}

Output:

Complexity Analysis:

Time Complexity:

The size of the list nums determines the time complexity of the xorGame function, which is denoted as O(N).

This is due to the implementation of the reduction function and the xor operator within the function, resulting in a linear time complexity for computing the xor of each element in the list.

Space Complexity:

• ✅ The spatial complexity of the function is determined to be O(1).
• ✅ Since the XOR operation is executed directly and only a fixed space is used for comparing with zero, there is no need for extra space relative to the input's size.