blob: a3048f774ec064e54cc1d8caa0103dd608667f3c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#include "leetcode.h"
/*
000 => {empty set}
001 => {set with only first element}
010 => {set with only second element}
011 => {set with first and second element}
100 ... and so on
101
110
111 => {subset with all three elements}
*/
class Solution {
public:
int subsetXORSum(vector<int> &nums) {
int n = nums.size(), subsetNum = pow(2, n), ans = 0;
for (int i = 1; i < subsetNum; ++i) {
int runningXOR = 0;
for (int j = 0, bits = i; j < nums.size(); ++j, bits >>= 1)
if (bits & 1)
runningXOR ^= nums[j];
ans += runningXOR;
}
return ans;
}
};
int main() {
vector<int> nums = {3, 4, 5, 6, 7, 8};
Solution obj;
cout << obj.subsetXORSum(nums);
}
|