Sum of All Subset XOR Totals
The key idea
Look at any single bit position. If at least one number has that bit set, then exactly half of all subsets XOR to a
1 in that position. So each bit that appears anywhere contributes to half the subsets, and the answer is OR(all numbers) * 2^(n-1).Problem
The XOR total of an array is 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 that 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.
Constraints
1 <= nums.length <= 121 <= nums[i] <= 20
Examples
Input: nums = [1,3]
Output: 6
Input: nums = [5,1,6]
Output: 28
Input: nums = [3,4,5,6,7,8]
Output: 480
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Bit Manipulation problems
- Bitwise AND of Numbers RangeMEDIUM
- Minimum Array EndMEDIUM
- Minimum Flips to Make a OR b Equal to cMEDIUM
- Missing NumberEASY
- Number of 1 BitsEASY
- Reverse BitsEASY
- Single NumberEASY
- Single Number IIMEDIUM
- Sum of Two IntegersMEDIUM