Game of XOR

Game of XOR | Practice | GeeksforGeeks

You are given an integer array arr[]. The value of a subarray is defined as the bitwise XOR of all elements in that subarray.Your task is to compute the bitwise XOR of the values of all possible subarrays of arr[]. Examples: Input: arr[] = [1, 2

https://www.geeksforgeeks.org/problems/game-of-xor1541/1

Problem

You are given an integer array arr[]. The value of a subarray is defined as the bitwise XOR of all elements in that subarray. Compute the bitwise XOR of the values of all possible subarrays of arr[].

Input	Output	Explanation
`[1,2,3]`	`2`	`Subarrays: (1), (1,2), (2), (2,3), (1,2,3), (3)` `XORs = 1,3,2,1,0,3` `Result = 1 ^ 3 ^ 2 ^ 1 ^ 0 ^ 3 = 2`
`[1,2]`	`0`	`Subarrays: (1), (1,2), (2) XORs , 3 , 2` `Result : 1 ^ 3 ^ 2 = 0`

Prerequisites

Bitwise XOR Properties

a ^ a = 0

a ^ 0 = a

XOR is associative: a ^ (b ^ c) = (a ^ b) ^ c

Order does not matter: a ^ b = b ^ a

RESOURCES

Bit Manipulation | LeetCode The Hard Way

CPH Bit Manipulation (extra)

Bit manipulation - CP Algorithms

CF - Raising Bacteria

Virtual Judge - Little Elephant and Bits

Virtual Judge - Maximizing Xor

CF - Preparing Olympiad

Virtual Judge - Red Scarf

Brute Force

Generate all subarrays and compute the XOR of each subarrays.

This is not feasible for the constraint n ≤ 10^5 , because time complexity is O(N^2)

Code


class Solution {
  public:
    int subarrayXor(vector<int>& arr) {
        int n = arr.size();
        int xr = 0;
        for(int i = 0; i < n; i++){
            int cur = 0;
            for(int j = i; j < n; j++){
                cur ^= arr[j];
                xr ^= cur;
            }
        }
        return xr;
    }
};

Optimal Approach

Hint

For an element, arr[i]: How many subarrays include arr[i]

Idea

We should compute the involvement of each number in the respective subarray. There are three conditions only:

The subarray starts from 0 to i of the array

The subarray ends at i to n-1 of the array

Therefore, for arr[i]:

Possible start positions: i+1

Possible end positions: n-i

So, total appearances in subarrays: count = (i+1)*(n-i)

If an element appears an even number of times, it cancels out in XOR. If it appears an odd times, it contributes to the final result.

Approach

While iterating, compute the occurrence of each element by (i+1)*(n-1)

If the occurrence is odd, then take XOR. Otherwise, they will cancel each other.

Return the final result.

Code


class Solution {
  public:
    int subarrayXor(vector<int>& arr) {
        int n = arr.size();
        int xr = 0;
        for(int i = 0; i < n; i++){
            int cnt = (i+1)*(n-i);
            if(cnt&1) xr ^= arr[i];
        }
        return xr;
    }
};

Time Complexity: O(N)

Space Complexity: O(1)

This approach only requires one pass through the array and constant extra storage.

Conclusion

Instead of building subarrays, the most efficient method is to compute the occurrence of each element in its subarrays and take only the odd occurrences for the XOR.

This greedy approach works because XORs at even count cancel each other out.