LeetCode 1863: Sum of All Subset XOR Totals

Subsets of numbers

For each subset we can xor the elements. If there are 3 numbers in the array, there are $2^3 = 8$ possible subsets. So, we use the bit patterns for the numbers $0, 1, 2, \ldots, 7$ to find elements of the subsets.

Time: $\mathcal{O}(2^n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def xor_total(self, subset, nums):
        s = 0
        for i in range(32):
            if subset & (1 << i):
                s ^= nums[i]
        return s

    def subsetXORSum(self, nums: List[int]) -> int:
        xor_sum = 0
        subset_count = 1 << len(nums)
        for subset in range(subset_count):
            xor_sum += self.xor_total(subset, nums)

        return xor_sum

Subsets of bit positions

Say we have two $(m+1)$ -bit numbers: $x = x_m \cdot 2^m + x_{m-1} \cdot 2^{m-1} + \cdots + x_1 \cdot 2^1 + x_0 \cdot 2^0$ and $y = y_m \cdot 2^m + y_{m-1} \cdot 2^{m-1} + \cdots + y_1 \cdot 2^1 + y_0 \cdot 2^0$ .

Now, XOR( $x$ , $y$ ) = $\text{XOR}(x_m, y_m) \cdot 2^m + \text{XOR}(x_{m-1}, y_{m-1}) \cdot 2^{m-1} + \cdots + \text{XOR}(x_1, y_1) \cdot 2^1 + \text{XOR}(x_0, y_0) \cdot 2^0$ .

Say, for the $n$ numbers, $k_i$ subset-xor’s have the $i$ -th bit set. So, in the final xor-sum the $i$ -th bit contributes $k_i \cdot 2^{i}$ . So, the sum we are looking for is $\sum_{i=0}^{32} k_i \cdot 2^i$ .

Say, $i$ -th bit is set in just one of the $n$ numbers. There are $2^{n-1}$ subsets which include that particular number and there are equal number of subsets that exclude that particular number. So, in the final xor-sum, the $i$ -th bit contributes: $2^{n-1} \cdot 2^i$ .

Now, if $i$ -th bit is set in two numbers, the xor will be unset if both of them are included. So, it seems the number of subsets that have xor-sum with $i$ -th bit set is less. But, the second number also adds to the count of subset where the first number is not included. These two, reduce and increase, nullify each other and we end up having $2^{n-1}$ subsets with $i$ -th bit set in their xor-sums.

In other words, whenever, $i$ -th bit is set in any of the $n$ numbers, it contributes $2^{n-1} \cdot 2^i$ to the final xor-sum.

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        xor_ones = 0
        for x in nums:
            xor_ones |= x
        
        return xor_ones << (len(nums)-1)

unreasonably effective