I was solving Sum of All Subset XOR Totals on Leetcode. It was obviously a Backtracking problem so I solved it in n*(2^n) . But it surprisingly has a linear solution. Like this
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
int sum=0;
for(auto i:nums)sum|=i;
return sum*(1<<(nums.size()-1));
}
};
Why this works ? Does anyone have the proof??
Consider single bit. If it's = 0 in all nums then it will contribute 0 to total sum, so we take only bits we have at least one 1. Xor of subset will equal to 1 if there is odd number of nums with this bit set, and of $$$2^n$$$ subsets, half of them will have even number of this bit, half odd. So total contribution of single bit is $$$\dfrac {2^n}2$$$