Scale Engineer

Sum of All Subset XOR Totals

Easy
#1702Time: 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: O(1), as we only use a few variables to store the state, requiring constant extra space.
Patterns
MathBacktrackingBit ManipulationCombinatoricsEnumeration
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as we only use a few variables to store the state, requiring constant extra space.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem