# Solution: Sum of All Subset XOR Totals

Let's solve the Sum of All Subset XOR Totals problem using the Bitwise Manipulation pattern.

## We'll cover the following

## Statement

Given an array of integers, `nums`

, compute and return the sum of XOR totals for all its possible subsets.

A

**subset**is any combination of elements from the original array,`nums`

. This includes the empty subset (containing no elements) and the subset that includes all array elements.The

**XOR total**of a subset results from applying the XOR operation to all the elements in that subset.

Note:If the`nums`

array has duplicate elements, then subsets that contain the same elements but with different indexes are treated as separate. Each subsetâ€™s XOR total is counted in the final sum.

**Constraints:**

$1 \leq$ `nums.length`

$\leq12$ $1 \leq$ `nums[i]`

$\leq 20$

## Solution

A naive approach to solving the problem would involve generating all possible subsets, calculating the XOR for each, and summing the results. However, with up to

To overcome this inefficiency, we use bitwise operations to determine how each number in the array contributes to the XOR total without generating all subsets. We can achieve this by using the properties of subset generation, binary numbers, and bitwise manipulation. The solution can be divided into two main parts:

**Bitwise OR:**XOR affects bits set to$1$ , so use bitwise OR to find each numberâ€™s contribution toward the XOR total. It identifies set ($1$ ) bits across the array.**The sum of XOR totals:**Left-shift the OR result (binary form) by ($n-1$ ) positions for the contribution of bits across all subsets (sum of XOR totals). Alternatively, we can multiply the decimal value of the result by$2^{nâ€“1}$ . This is because each number in an array appears in exactly half of the possible subsets, which is$2^{nâ€“1}$ .

Once we know which bits are set, we donâ€™t need to explicitly compute the XOR for each subset. We know these active bits will affect the XOR total, and we can calculate their combined effect directly. For this, we multiply the OR result by

Let's look at the algorithm steps given below:

Initialize a variable

`output`

to$0$ . This variable will store the cumulative OR result of all numbers in the array.Iterate over the array, and for each number

`num`

, perform a bitwise OR operation between`output`

and`num`

. Update`output`

with the result. This step collects all bits that could potentially influence the XOR of any subset.After processing all the numbers, left shift (<<) the

`output`

by`(len(nums) - 1)`

bits, and return the`output`

. Alternatively, we can multiply the`output`

with$2^{len(nums)-1}$ to get the final value.

The slides below help to understand the solution in a better way.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.