Subset XOR sum

Compute the sum of XOR totals of all non-empty subsets of a list of integers.

xor bitwise subsets iteration

Write a function `subset_xor_sum(nums)` that takes a list of non-negative integers and returns the sum of the XOR totals of every non-empty subset of `nums`.

For a subset, its XOR total is defined as the bitwise XOR of all its elements. For example, the XOR total of the subset [5, 2] is 5 xor 2 = 7. The empty subset has XOR total 0, but it is excluded from the sum.

You may assume that `nums` has at most 12 elements, so you can enumerate all subsets directly.

Return the result as an integer.

Constraints

0 <= len(nums) <= 12
0 <= each element <= 10^3
The result fits in a standard 32-bit signed integer.

Example

>>> subset_xor_sum([1, 3])
6
>>> subset_xor_sum([5, 1, 6])
28
>>> subset_xor_sum([0])
0

8 points ~10 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

There are 2^n non-empty subsets. Use a bitmask to represent which elements are in each subset.

For each mask from 1 to (1<<n)-1, compute the XOR of nums[i] where the i-th bit of the mask is set.

Accumulate the XOR totals into a sum and return it.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.