All Subsets Xor Sum

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Sum of XOR of all subsets equals (bitwise OR of all elements) * 2^(n-1).

Algorithm

1Compute OR of all elements. Multiply by 2^(n-1).

Common Pitfalls

•Mathematical insight: each bit that appears in any element contributes 2^(n-1) to the total XOR sum.

All Subsets Xor Sum.java

Java

// Approach: Each bit in elements contributes independently. Total XOR sum = OR of all elements * 2^(n-1).
// Time: O(n) Space: O(1)
class Solution {
    int subsetXORSum(int arr[]) {
        int or = 0;
        for (int x : arr) {
            or |= x;
        }

        int n = arr.length;
        return or * (1 << (n - 1));
    }
}

Was this solution helpful?