**Sum of All Subset XOR Totals**

Check the problem description here.

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)*