Sum of All Subset XOR Totals

EASY

Description

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

1 <= nums.length <= 12
1 <= nums[i] <= 20

Approaches

Checkout 3 different approaches to solve Sum of All Subset XOR Totals. Click on different approaches to view the approach and algorithm in detail.

Brute Force using Bitmasking

This approach systematically generates every possible subset of the input array nums. Since an array of size n has 2^n subsets, we can use an integer from 0 to 2^n - 1 as a bitmask to represent each subset. Each bit in the mask corresponds to an element in nums. If the j-th bit is set, the j-th element is included in the subset.

Algorithm

Initialize totalSum = 0.
Let n be the length of nums.
Iterate with a variable i from 0 to 2^n - 1. This i acts as a bitmask.
For each i, initialize currentXorTotal = 0.
Iterate with a variable j from 0 to n - 1.
If the j-th bit of i is set, update currentXorTotal by XORing it with nums[j].
After the inner loop, add currentXorTotal to totalSum.
Return totalSum.

We iterate through all possible bitmasks from 0 to 2^n - 1. For each mask, we calculate the XOR total of the corresponding subset by iterating through the elements of nums. If the bit corresponding to an element is set in the mask, we include it in the XOR calculation. The calculated XOR total is then added to a running sum. After checking all 2^n masks, the total sum is the final answer.

class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int totalSum = 0;
        // There are 2^n subsets, represented by numbers from 0 to 2^n - 1.
        int numSubsets = 1 << n; // Equivalent to 2^n

        // Iterate through all possible subsets using a bitmask.
        for (int i = 0; i < numSubsets; i++) {
            int currentXorTotal = 0;
            for (int j = 0; j < n; j++) {
                // Check if the j-th element is in the current subset.
                // (i >> j) & 1 checks if the j-th bit of i is 1.
                if (((i >> j) & 1) == 1) {
                    currentXorTotal ^= nums[j];
                }
            }
            totalSum += currentXorTotal;
        }
        return totalSum;
    }
}

Complexity Analysis

Time Complexity: O(n * 2^n), where `n` is the number of elements in `nums`. We have an outer loop that runs `2^n` times and an inner loop that runs `n` times.Space Complexity: O(1), as we only use a few variables to store the state, requiring constant extra space.

Pros and Cons

Pros:

Simple to understand and implement iteratively.
Uses constant extra space.

Cons:

Inefficient for larger n due to its O(n * 2^n) time complexity.
It's the slowest among the valid approaches for this problem.

Code Solutions

Checking out 4 solutions in different languages for Sum of All Subset XOR Totals. Click on different languages to view the code.

class Solution {
public
  int subsetXORSum(int[] nums) {
    int n = nums.length;
    int ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int s = 0;
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          s ^= nums[j];
        }
      }
      ans += s;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Sum of All Subset XOR Totals

Patterns:

MathBacktrackingBit ManipulationCombinatoricsEnumeration

Data Structures:

Array