Total of Subset XORs

EasyBacktracking

Problem

For any group of numbers, define its XOR value as the bitwise XOR of all its members (the empty group has XOR value 0).

Given nums, compute the XOR value of every subset of nums (subsets are chosen by position, so equal values at different positions give different subsets) and return the sum of all of them.

Example 1

Input:
nums = [1, 3]
Output:
6

Subsets: [] → 0, [1] → 1, [3] → 3, [1, 3] → 1 XOR 3 = 2. Sum = 0 + 1 + 3 + 2 = 6.

Example 2

Input:
nums = [5, 1, 6]
Output:
28

Constraints

  • 1 ≤ nums.length ≤ 12
  • 0 ≤ nums[i] ≤ 2^12

Hint

Show the first hint

You do not need to store the subsets, only their XOR values.

Walkthrough

How to approach it

01Clarify before coding

  • Is the empty subset included? Yes, it contributes 0.
  • Do duplicate values make separate subsets? Yes, subsets are chosen by position.
  • Can the sum overflow? With n ≤ 12 and values < 2^13, the sum is below 2^12 · 2^13, which fits easily.

02Brute force

Generate every subset as a list, then XOR its members.

Cost: O(n · 2^n) time and the same memory if you keep the lists; the lists themselves are never needed.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.