Sum of All Subset XOR Totals
EasyPrompt
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]is2 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 = 6Example 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 = 28Example 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 <= 121 <= 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
nbe the length ofnums. - Iterate with a variable
ifrom0to2^n - 1. Thisiacts as a bitmask. - For each
i, initializecurrentXorTotal = 0. - Iterate with a variable
jfrom0ton - 1. - If the
j-th bit ofiis set, updatecurrentXorTotalby XORing it withnums[j]. - After the inner loop, add
currentXorTotaltototalSum. - 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
ndue to itsO(n * 2^n)time complexity.It's the slowest among the valid approaches for this problem.
A more elegant way to explore all subsets is through recursion. We can define a function that builds subsets by making a decision for each element: either include it in the current subset or exclude it. This naturally forms a decision tree where each path from the root to a leaf represents a unique subset.
Algorithm
- Define a recursive function
dfs(nums, index, currentXor). - Base Case: If
indexequalsnums.length, returncurrentXor. - Recursive Step:
- Calculate the sum for subsets including
nums[index]:sum1 = dfs(nums, index + 1, currentXor ^ nums[index]). - Calculate the sum for subsets excluding
nums[index]:sum2 = dfs(nums, index + 1, currentXor). - Return
sum1 + sum2.
- Calculate the sum for subsets including
- Initiate the recursion with
dfs(nums, 0, 0).
Walkthrough
We use a recursive function, say dfs(index, currentXor), which calculates the sum of XOR totals for all subsets that can be formed from the elements nums[index:]. The currentXor parameter keeps track of the XOR total of the subset formed so far.
For each element nums[index], we make two recursive calls:
- One that includes
nums[index]in the subset:dfs(index + 1, currentXor ^ nums[index]). - One that excludes
nums[index]:dfs(index + 1, currentXor). The base case for the recursion is whenindexreaches the end of the array. At this point, we have a complete subset, and its XOR total iscurrentXor. We return this value. The sum of the results from the two recursive calls gives the total sum for the current state.
class Solution { public int subsetXORSum(int[] nums) { return dfs(nums, 0, 0); } /** * Helper function to compute the sum of XOR totals recursively. * @param nums The input array. * @param index The current index in the array to consider. * @param currentXor The XOR total of the subset built so far. * @return The sum of XOR totals for all subsets starting from the current state. */ private int dfs(int[] nums, int index, int currentXor) { // Base case: If we have processed all elements, we have formed one complete subset. // The XOR total for this subset is currentXor. Return it to be summed up. if (index == nums.length) { return currentXor; } // Recursive step: // Case 1: Include the current element nums[index] in the subset. // The new XOR total will be currentXor ^ nums[index]. int sumWithElement = dfs(nums, index + 1, currentXor ^ nums[index]); // Case 2: Exclude the current element nums[index] from the subset. // The XOR total remains the same. int sumWithoutElement = dfs(nums, index + 1, currentXor); // The total sum is the sum of the results from both cases. return sumWithElement + sumWithoutElement; }}Complexity
Time
O(2^n). The recursive function is called `2^(n+1) - 1` times, creating a complete binary tree of calls. Each call does constant work.
Space
O(n) due to the recursion depth, which can go up to `n`.
Trade-offs
Pros
More time-efficient than the bitmasking approach.
The code is concise and reflects the problem's structure well.
Cons
Uses
O(n)space for the call stack, which is more than the iterative bitmasking approach.
This approach avoids generating subsets altogether by analyzing the contribution of each bit position to the final sum. For any given bit position k, we determine how many subset XOR totals will have this bit set.
Algorithm
- Initialize
orValue = 0. - Iterate through each number
numin thenumsarray and compute the bitwise OR of all of them:orValue |= num. - Let
nbe the length ofnums. - Calculate the multiplier
mult = 1 << (n - 1), which is2^(n-1). - The final answer is
orValue * mult.
Walkthrough
Let's consider the i-th bit. A subset's XOR total will have the i-th bit set if an odd number of elements in that subset have their i-th bit set.
It can be shown that if at least one number in the input array nums has the i-th bit set, then exactly half of all possible subsets will have an XOR total where the i-th bit is 1. The total number of subsets is 2^n, so 2^(n-1) subsets will have the i-th bit set in their XOR total.
The contribution of the i-th bit to the final sum is therefore (number of subsets) * (value of the bit), which is 2^(n-1) * 2^i.
Summing this over all bits i that are set in at least one number in nums gives the total sum.
This can be simplified: Sum = Σ (2^(n-1) * 2^i) = 2^(n-1) * Σ 2^i.
The term Σ 2^i is simply the bitwise OR of all numbers in nums.
So, the final result is (nums[0] | nums[1] | ... | nums[n-1]) * 2^(n-1).
class Solution { public int subsetXORSum(int[] nums) { int n = nums.length; int orValue = 0; // Calculate the bitwise OR of all elements in the array. for (int num : nums) { orValue |= num; } // The result is the OR value multiplied by 2^(n-1). // 1 << (n - 1) is a fast way to compute 2^(n-1). return orValue * (1 << (n - 1)); }}Complexity
Time
O(n), as we only need to iterate through the array once to compute the bitwise OR.
Space
O(1), as we only use a few variables, requiring constant extra space.
Trade-offs
Pros
Extremely efficient with linear time complexity.
It's the optimal solution.
Uses constant space.
Cons
The logic is less intuitive and requires some combinatorial insight to derive.
Solutions
Solution
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; }}/** * @param {number[]} nums * @return {number} */ var subsetXORSum = function ( nums,) { let ans = 0; const n = nums.length; for (let i = 0; i < 1 << n; ++i) { let s = 0; for (let j = 0; j < n; ++j) { if ((i >> j) & 1) { s ^= nums[j]; } } ans += s; } return ans;};class Solution {public: int subsetXORSum(vector<int> &nums) { int n = nums.size(); 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) { s ^= nums[j]; } } ans += s; } return ans; }};class Solution: def subsetXORSum(self, nums: List[int]) -> int: ans, n = 0, len(nums) for i in range(1 << n): s = 0 for j in range(n): if i >> j & 1: s ^= nums[j] ans += s return ansVideo 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.