Sum of All Subset XOR Totals — Problem & Solution
Sum of All Subset XOR Totals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Sum of All Subset XOR Totals is an easy coding problem on arrays, math and bit manipulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Bit Manipulation, Backtracking, Combinatorics
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The XOR total of an array is the bitwise XOR of all its elements; the empty array has XOR total 0.
Given an array nums, return the sum of the XOR totals over every subset of nums. Subsets with the same elements at different indices are counted separately.
Example 1
Input: nums = [1,3]
Output: 6
Explanation: The subsets give 0, 1, 3 and 2.
Example 2
Input: nums = [5,1,6]
Output: 28
Example 3
Input: nums = [3,4,5,6,7,8]
Output: 480
Constraints
1 <= nums.length <= 201 <= nums[i] <= 20
Follow-up: Enumerating all 2^n subsets works for n ≤ 20. Can you find the closed form?
Hints for Sum of All Subset XOR Totals
Hint 1
Enumerating the
2^nsubsets is fine here, but look at one bit position at a time.Hint 2
If any element has a given bit set, exactly half of all subsets end up with that bit set in their XOR.
Hint 3
So the answer is
(nums[0] | nums[1] | … ) * 2^(n-1).
How to solve Sum of All Subset XOR Totals
For each bit that appears in at least one element, exactly half of all subsets have that bit set in their XOR; the answer is (OR of all) · 2^(n-1).
Approach
- OR all elements.
- Shift left by
n - 1.
Why it works
Fix an element with the bit set; pairing each subset with the one obtained by toggling that element's membership flips the XOR bit, so subsets split evenly. Bits present in no element contribute nothing.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Enumerating
2^nsubsets is fine at this size but misses the point.
Reference solution
Python
def subsetXORSum(nums) -> int:
or_all = 0
for x in nums:
or_all |= x
return or_all << (len(nums) - 1)Java
public static int subsetXORSum(int[] nums) {
int orAll = 0;
for (int x : nums) orAll |= x;
return orAll << (nums.length - 1);
}C++
int subsetXORSum(vector<int>& nums) {
int orAll = 0;
for (int x : nums) orAll |= x;
return orAll << ((int) nums.size() - 1);
}JavaScript
var subsetXORSum = function(nums) {
let orAll = 0;
for (let i = 0; i < nums.length; i++) orAll |= nums[i];
return orAll * Math.pow(2, nums.length - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation