XOR of the XORs of all Possible Subsets of the Array

Problem Statement

Given an array of integers, find the XOR of the XORs of all possible subsets of the array.

A subset can be of any size, including the empty set, For each subset, compute the XOR of its elements. Then, XOR all those results together and return the final result.

Constraints:

• 1 ≤ arr.length ≤ 10^5
• 0 ≤ arr[i] ≤ 10^9

Examples

Example 1:

Input: arr = [1, 2]
Subsets and XORs:
{}        → 0
{1}       → 1
{2}       → 2
{1, 2}    → 1 ^ 2 = 3

Final XOR: 0 ^ 1 ^ 2 ^ 3 = 0
Output: 0

Example 2:

Input: arr = [5]
Subsets: {}, {5}
XORs:    0, 5
Final XOR: 0 ^ 5 = 5
Output: 5

Example 3:

Input: arr = [1, 2, 3]
All subset XORs: 0, 1, 2, 3, 1^2, 1^3, 2^3, 1^2^3 → XOR them all → 0
Output: 0

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Generate all subsets, compute XOR of each, and XOR all those result.

Code:

#include <iostream>
#include <vector>
using namespace std;

int bruteForceSubsetXOR(vector<int>& arr) {
    int n = arr.size();
    int result = 0;
    int total = 1 << n; // total subsets = 2^n

    for (int mask = 0; mask < total; ++mask) {
        int subsetXOR = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                subsetXOR ^= arr[i];
            }
        }
        result ^= subsetXOR;
    }
    return result;
}

Complexity Analysis:

• Time Complexity:O(2 ^ n * n)
  • Exponential
• Space Complexity:O(1)

2️⃣ Optimal Approach

Intuition:

Use XOR properties and frequency of each element.

Code:

#include <iostream>
#include <vector>
using namespace std;

int xorOfAllSubsetXORs(const vector<int>& arr) {
    int n = arr.size();
    if (n == 0) return 0;
    if (n == 1) return arr[0];
    return 0; // when n > 1, every element appears even number of times
}

Complexity Analysis:

• Time Complexity:O(1)
• Space Complexity:O(1)