Daily Archives: September 5, 2021

1863. Sum of All Subset XOR Totals

key idea is how to generate all subset of array.

take 3 elements of arrays for example,

[a, _, _] -> [1, 0, 0]
[_, b, _] -> [0, 1, 0]
[a, b, _] -> [1, 1, 0]
[_, _, c] -> [0, 0, 1]
[a, _, c] -> [1, 0, 1]
[_, b, c] -> [0, 1, 1]
[a, b, c] -> [1, 1, 1]

integer i is loop through 1 to Math.pow(2, nums.length) – 1, for each integer, we check how many 1 bit

i & 1, if it is 1, we get nums[index] out as elements for subarray.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
class Solution {
    public int subsetXORSum(int[] nums) {
        int result = 0;
    	int x = (int)Math.pow(2, nums.length) - 1;
        for(int i=1;i<=x;i++) {
        	int p = i;
        	int r = 0;
        	for(int j=0;j<nums.length;j++) {
        		int t = p & 1;
        		p >>= 1;
 
        		if (t == 1) {
    				r ^= nums[j];
        		}
        	}
 
        	result += r;
        }
 
        return result;
    }
}