Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Sum of All Subset XOR Totals

Sum of All Subset XOR Totals

Master this topic with zero to advance depth.

Sum of All Subset XOR Totals

Return the sum of all XOR totals for every subset of nums.

Easy

Examples

Input: nums = [1,3]
Output: 6
Input: nums = [5,1,6]
Output: 28
Approach 1

Level I: Brute Force (Backtracking)

Intuition

Generate all possible 2n2^n subsets, calculate the XOR of each, and sum them up.

Thought Process

  1. Use recursion to explore including or excluding each element.
  2. Maintain a currentXor value through the recursion tree.
  3. Base case: If reached end of array, return currentXor.

Pattern: Subset Generation

⏱ O(2^N) - We visit every subset.💾 O(N) - Recursion depth.
java
public class Solution {
    public int subsetXORSum(int[] nums) {
        return backtrack(nums, 0, 0);
    }
    
    private int backtrack(int[] nums, int index, int currentXor) {
        if (index == nums.length) return currentXor;
        // sum of (XORs including nums[index]) + (XORs excluding nums[index])
        return backtrack(nums, index + 1, currentXor ^ nums[index]) + 
               backtrack(nums, index + 1, currentXor);
    }
}
Approach 2

Level II: Iterative Subset Generation

Intuition

Use a bitmask from 0 to 2n−12^n - 1 to represent every possible subset of nums. For each mask, calculate the XOR total and add it to the sum.

⏱ $O(N \cdot 2^N)$💾 $O(1)$
java
class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length, total = 0;
        for (int i = 0; i < (1 << n); i++) {
            int current = 0;
            for (int k = 0; k < n; k++) {
                if (((i >> k) & 1) == 1) current ^= nums[k];
            }
            total += current;
        }
        return total;
    }
}
Approach 3

Level III: Optimal (Contribution of Each Bit)

Intuition

For a bit position ii, if at least one number in nums has the ii-th bit set, then in exactly half of the 2n2^n subsets (i.e., 2n−12^{n-1}), the XOR total will have the ii-th bit set. This is because adding a number with the ii-th bit set flips the ii-th bit of the XOR sum.

Thought Process

  1. Find the bitwise OR of all numbers in the array. This identifies all bit positions that are set in at least one number.
  2. If the ii-th bit is set in the OR result, it contributes 2i⋅2n−12^{i} \cdot 2^{n-1} to the total sum.
  3. Result = (OR of all nums) * 2^(n-1).

Pattern: Combinatorial Bit Counting

⏱ O(N) - Single pass to find the bitwise OR.💾 O(1) - Constant space.

Detailed Dry Run

nums = [1, 3], n = 2 OR = 1 | 3 = 3 (binary 11) Sum = 3 * 2^(2-1) = 3 * 2 = 6. Result matches brute force!

java
public class Solution {
    public int subsetXORSum(int[] nums) {
        int res = 0;
        for (int x : nums) res |= x;
        return res << (nums.length - 1);
    }
}
← Previous QuestionMinimum Flips to Make a OR b Equal to c
Next Question →Reverse Pairs