Sum of XOR of all possible subsets

We are given an array arr[], find the sum of XOR values of all possible subsets of the array.

Note: Every subset formed using different index selections must be considered separately, even if two subsets contain the same elements.

Examples:

Input: arr[] = [1, 2, 3]
Output: 12
Explanation: All possible subsets are: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
Bitwise-XOR of these subsets will be: 0, 1, 2, 3, 3, 2, 1, 0, 12 respectively.
Sum of all these XOR values will be 12(0 + 1 + 2 + 3 + 3 + 2 + 1 + 0).

Input: arr[] = [7, 2]
Output: 14
Explanation: All possible subsets are: [[], [7], [2], [7, 2]]
There Bitwise-XOR will be: 0, 7, 2 and 5 respectively.
Sum of all these XOR values will be 14(0 + 7 + 2 + 5).

[Naive Approach] - Exploring All Possible Subsets - O(2^n) Time and O(n) Space

We can use recursion to explore all possible subsets. At each step, we will decide whether to include or exclude the current element, and we update the running XOR value based on that choice. This allows us to compute the XOR contribution of every subset. By returning the sum of the results from both choices i.e. one including the element and one excluding it - we accumulate the total XOR sum of all subsets.

#include<iostream>
#include <vector>

using namespace std;

int xorRecur(int i, int xorOfSubset, vector<int> &arr) {
    if (i==arr.size()) return xorOfSubset;
    
    // subset having current element
    int subset1 = xorRecur(i+1, xorOfSubset ^ arr[i], arr);
    
    // subset not having current element
    int subset2 = xorRecur(i+1, xorOfSubset, arr);
    
    // return sum of both
    return subset1 + subset2;
}

int subsetXORSum(vector<int> &arr) {
    
    // Recursively find the sum 
    // of xor of all the subsets
    return xorRecur(0, 0, arr);
}

int main() {
    vector<int> arr = {1, 2, 3};
    cout << subsetXORSum(arr) << endl;
    return 0;
}

class GFG {

    static int xorRecur(int i, int xorOfSubset, int[] arr) {
        if (i == arr.length) return xorOfSubset;
        
        // subset having current element
        int subset1 = xorRecur(i + 1, xorOfSubset ^ arr[i], arr);

        // subset not having current element
        int subset2 = xorRecur(i + 1, xorOfSubset, arr);

        // return sum of both
        return subset1 + subset2;
    }

    static int subsetXORSum(int[] arr) {

        // Recursively find the sum 
        // of xor of all the subsets
        return xorRecur(0, 0, arr);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(subsetXORSum(arr));
    }
}

def xorRecur(i, xorOfSubset, arr):
    if i == len(arr):
        return xorOfSubset

    # subset having current element
    subset1 = xorRecur(i + 1, xorOfSubset ^ arr[i], arr)

    # subset not having current element
    subset2 = xorRecur(i + 1, xorOfSubset, arr)

    # return sum of both
    return subset1 + subset2


def subsetXORSum(arr):

    # Recursively find the sum 
    # of xor of all the subsets
    return xorRecur(0, 0, arr)

if __name__ == "__main__":
    arr = [1, 2, 3]
    print(subsetXORSum(arr))

using System;
using System.Collections.Generic;

class GFG {

    static int xorRecur(int i, int xorOfSubset, List<int> arr) {
        if (i == arr.Count) return xorOfSubset;

        // subset having current element
        int subset1 = xorRecur(i + 1, xorOfSubset ^ arr[i], arr);

        // subset not having current element
        int subset2 = xorRecur(i + 1, xorOfSubset, arr);

        // return sum of both
        return subset1 + subset2;
    }

    static int subsetXORSum(List<int> arr) {

        // Recursively find the sum 
        // of xor of all the subsets
        return xorRecur(0, 0, arr);
    }

    static void Main() {
        List<int> arr = new List<int> { 1, 2, 3 };
        Console.WriteLine(subsetXORSum(arr));
    }
}

function xorRecur(i, xorOfSubset, arr) {
    if (i === arr.length) return xorOfSubset;

    // subset having current element
    let subset1 = xorRecur(i + 1, xorOfSubset ^ arr[i], arr);

    // subset not having current element
    let subset2 = xorRecur(i + 1, xorOfSubset, arr);

    // return sum of both
    return subset1 + subset2;
}

function subsetXORSum(arr) {

    // Recursively find the sum 
    // of xor of all the subsets
    return xorRecur(0, 0, arr);
}

// Driver code
let arr = [1, 2, 3];
console.log(subsetXORSum(arr));

12

[Expected Approach] - Bit Contribution - O(n) Time and O(1) Space

The idea is to determine how many subsets will have a particular bit set in their XOR value. A bit contributes to the XOR only when it appears an odd number of times in a subset. So, if a bit appears k times in the array, it can contribute when it is chosen 1, 3, 5, ... times in the subset—up to at most k times. By counting how many subsets produce an odd occurrence for each bit, and repeating this process for every bit position, we can compute the total contribution of each bit and sum these contributions to get the final XOR sum of all subsets.

• Lets assume there are k elements in the array with i'th bit set and k > 0. 
• So, to have a subset with i'th bit set in its xor, we need it to have odd number of elements with i'th bit set.
• Number of ways to choose elements that don't have i'th bit set = 2^(n-k), (n-k) is the number of elements with i'th bit as unset.
• Number of ways to choose elements with i'th bit as set = ^kC₁ + ^kC₃ + ^kC₅ .... = 2^(k-1)
• Total number of ways = 2^(n-k) * 2^(k-1) = 2^(n-1).
• Thus, the contribution of i'th bit in sum becomes, 2^(n-1) * 2 ⁱ = 2 ^(n+i-1)

Therefore, we first take the bitwise OR of all numbers to gather every bit that appears anywhere, and then multiply it by 2^(n-1) to get the final sum.

Examples: 

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

int subsetXORSum(vector<int> &arr) {
    int n = arr.size();
    int bits = 0;

    // Finding bitwise OR of all elements
    for (int i=0; i < n; ++i)
        bits |= arr[i];

    int ans = bits * pow(2, n-1);

    return ans;
}

int main() {
    vector<int> arr = {1, 2, 3};
    cout << subsetXORSum(arr) << endl;
    return 0;
}

class GFG {
    static int subsetXORSum(int[] arr) {
        int n = arr.length;
        int bits = 0;

        // Finding bitwise OR of all elements
        for (int i = 0; i < n; ++i)
            bits |= arr[i];

        int ans = (int)(bits * Math.pow(2, n - 1));

        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        System.out.println(subsetXORSum(arr));
    }
}

def subsetXORSum(arr):
    n = len(arr)
    bits = 0

    # Finding bitwise OR of all elements
    for i in range(n):
        bits |= arr[i]

    ans = bits * (2 ** (n - 1))

    return ans

if __name__ == "__main__":
    arr = [1, 2, 3]
    print(subsetXORSum(arr))

using System;

class GfG {
    static int subsetXORSum(int[] arr) {
        int n = arr.Length;
        int bits = 0;

        // Finding bitwise OR of all elements
        for (int i = 0; i < n; ++i)
            bits |= arr[i];

        int ans = (int)(bits * Math.Pow(2, n - 1));

        return ans;
    }

    static void Main(string[] args) {
        int[] arr = {1, 2, 3};
        Console.WriteLine(subsetXORSum(arr));
    }
}

function subsetXORSum(arr) {
    let n = arr.length;
    let bits = 0;

    // Finding bitwise OR of all elements
    for (let i = 0; i < n; ++i)
        bits |= arr[i];

    let ans = bits * Math.pow(2, n - 1);

    return ans;
}

// Driver code
const arr = [1, 2, 3];
console.log(subsetXORSum(arr));

12