Sum of All Subset XOR Totals
Each bit set in any element appears in exactly half the subsets — answer is OR-of-all-bits times 2^(n-1).
2 min read
bit-manipulation combinatorics
Problem#
Sum of XOR totals across all 2^n subsets of nums.
Examples#
[1,3]→6(subsets: [], [1], [3], [1,3] → 0+1+3+2=6).[5,1,6]→28;[3,4,5,6,7,8]→480.
Constraints#
1 <= nums.length <= 12,1 <= nums[i] <= 20.
Approach#
Bit-by-bit: a bit position is set in the XOR of a subset iff an odd number of selected elements have that bit. If at least one element has that bit, exactly half the 2^n subsets satisfy “odd count” — 2^(n-1) of them. So contribution per set bit b is 2^b * 2^(n-1). The OR of all elements collects which bit positions ever appear.
Solution#
class Solution {public: int subsetXORSum(vector<int>& nums) { int orAll = 0; for (int v : nums) orAll |= v; return orAll << (nums.size() - 1); }};func subsetXORSum(nums []int) int { orAll := 0 for _, v := range nums { orAll |= v } return orAll << (len(nums) - 1)}from typing import List
class Solution: def subsetXORSum(self, nums: List[int]) -> int: or_all = 0 for v in nums: or_all |= v return or_all << (len(nums) - 1)function subsetXORSum(nums) { let orAll = 0; for (const v of nums) orAll |= v; return orAll << (nums.length - 1);}class Solution { public int subsetXORSum(int[] nums) { int orAll = 0; for (int v : nums) orAll |= v; return orAll << (nums.length - 1); }}function subsetXORSum(nums: number[]): number { let orAll: number = 0; for (const v of nums) orAll |= v; return orAll << (nums.length - 1);}Editorial#
A beautiful collapse: the combinatorial sum sum over subsets of XOR(subset) reduces to a single shift on OR(nums). The proof is per-bit independence — each bit contributes independently, and once at least one element has the bit, half the subsets flip it on.
Complexity#
- Time:
O(n). - Space:
O(1).
Concept revision#
Related#