Sum of All Subset XOR Totals

Check the problem description here.

Sum of All Subset XOR Totals - LeetCode

There are many approaches for this problem.

Approach 1:

Naive solution

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        length = len(nums)
        result=0
        for i in range(2**length):
            binary = bin(i)[2:]
            if(len(binary)<length):
                binary = ((length-len(binary))*"0")+binary
            xor_=0
            for i in range(len(binary)):
                if binary[i]=="1":
                    xor_^=nums[i]
            result+=xor_
        return(result)

Time: O(n*2^n)

Space: O(1)

Approach 2:

Bit masking

The same approach we followed , above can also be done using the concept of bit masking.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        length = len(nums)
        result=0
        for i in range(1<<length):
            xor_=0
            for j in range(length):
                if( i & 1<<j !=0 ):
                    xor_^=nums[j]
            result+=xor_
        return(result)

Time: O(n*2^n)

Space: O(1)

Approach:

The most optimized solution.

n= number of elements in the set

We also know there are 2^n subset for a set, then, possibly we have 2^n XOR results that need to be summed to get the final result. Now we come to a property that, for any number in the given nums list , if it has ‘i th’ bit as set, then , out of the 2^n XOR results, 2^(n-1) will have the ‘i th’ bit set. So ideally we should find which bit positions are set in the XOR results, which can be done using “OR” of all the numbers in the nums. Then to get the final result , we sum up , 2^(n-1)*place-value of the bit positions , for all the bit position for which it is set . Here 2^(n-1) is used in above formula , since that bit position repeat 2^(n-1) out of all the 2**n XOR results.

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        total,length=0,len(nums)
        for i in nums:
            total|=i
        return(2**(length-1)*total)

Time: O(n)

Space: O(1)