Loading…

mediumBit ManipulationLC #1863Sometimes asked

Sum of All Subset XOR Totals

Q: How do you solve Sum of All Subset XOR Totals using the Brute Force — Enumerate All Subsets approach?

When to use it: State it first to show you understand the definition, then say 'this is exponential; we can collapse it'. Translate the definition directly into code by walking every subset. **Encode subsets as bitmasks.** A mask from 0 to 2ⁿ - 1 represents a subset: if bit j is set, include nums[j]. Mask 0 is the empty subset; the all-ones mask is the full array. **XOR the chosen elements.** For each mask, scan its set bits and XOR the corresponding values into a subset total. Add that total to the grand sum. **Why this is the honest baseline.** It mirrors the problem statement one-to-one and is correct for any n. With n ≤ 12 it even passes. But it does exponential work, and the interviewer wants you to notice the structure that makes it collapse. **Where it breaks down.** At larger n, 2ⁿ is hopeless. That pressure is the cue to analyze bits independently instead of enumerating subsets. Time complexity: O(2ⁿ · n). Space complexity: O(1).

Q: How do you solve Sum of All Subset XOR Totals using the Per-Bit Counting — OR × 2ⁿ⁻¹ (Optimal) approach?

When to use it: The answer they want. Phrase it as 'each bit in the OR shows up in exactly half the subset XORs'. Decompose the sum bit by bit, because XOR acts on each bit independently. **Fix one bit position b.** A subset's XOR total has bit b set exactly when the subset contains an **odd number** of elements whose bit b is 1. Bits are independent under XOR, so we can total each bit's contribution separately and add them up. **Case 1: no element has bit b.** Then no subset can ever set bit b in its XOR — bit b contributes 0 to every subset. Notice 'some element has bit b' is precisely 'the OR of all elements has bit b'. **Case 2: at least one element has bit b.** Say `k ≥ 1` elements have bit b set. A subset sets bit b iff it picks an odd number of those `k` elements. The number of ways to pick an odd-sized subset from `k` items is `2^{k-1}`, and the remaining `n - k` elements are each free (in or out), giving `2^{n-k}` choices. So the count of subsets that set bit b is `2^{k-1} × 2^{n-k} = 2^{n-1}` — exactly half of all 2ⁿ subsets, independent of `k`. **Combine.** Each bit present in the OR contributes `2^b` to `2^{n-1}` subsets, i.e. `2^b × 2^{n-1}`. Summing over all set bits of the OR factors out the `2^{n-1}`: the answer is `OR(all elements) × 2^{n-1}`, which is just `OR << (n - 1)`. The empty subset contributes 0 and is already accounted for in the half-count. Time complexity: O(n). Space complexity: O(1).

LCPractice

Bit Manipulation · 12 of 20 · 10 min

The XOR total of an array is the bitwise XOR of all its elements; the XOR total of an empty array is 0.

Given an array nums, return the sum of the XOR totals of every subset of nums. Subsets with the same elements but different indices are counted separately.

In plain English

Consider all 2ⁿ subsets (including the empty one). For each, compute the XOR of its elements; sum those values. The small constraints allow brute force, but the elegant answer comes from analyzing each bit position independently and counting how many subsets set it.

Examples

Example 1

Input: nums = [1, 3]
Output: 6
Note: Subsets: {}→0, {1}→1, {3}→3, {1,3}→2. Sum = 0+1+3+2 = 6. Check: OR(1,3)=3, ×2¹ = 6.

Example 2

Input: nums = [5, 1, 6]
Output: 28
Note: OR(5,1,6) = 7, n = 3, so 7 × 2² = 28.

Example 3

Input: nums = [3, 4, 5, 6, 7, 8]
Output: 480
Note: OR of all = 15, n = 6, so 15 × 2⁵ = 15 × 32 = 480.

Constraints

1 ≤ nums.length ≤ 12
1 ≤ nums[i] ≤ 20
There are 2ⁿ subsets, including the empty subset

Clarifying questions4First question: Is the empty subset included?Explore questions

Q1.Is the empty subset included?
Yes, but its XOR total is 0, so it adds nothing. Including or excluding it gives the same sum.
Q2.Are subsets distinguished by index or by value?
By index — duplicate values at different positions form distinct subsets. The counting argument naturally treats each element independently.
Q3.How large is n?
Up to 12 here, so even 2ⁿ ≈ 4096 brute force is fine. I'll show it, then give the O(n) closed form.
Q4.Can values be 0 or negative?
Values are positive per constraints. The bit argument would still hold for 0; negatives would need care with the sign bit, but that's out of scope here.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Sum the XOR of every one of the 2ⁿ subsets. The O(n) answer: a bit contributes to the total only if at least one element has it set, and when it does, exactly half of all subsets (2ⁿ⁻¹ of them) have that bit set in their XOR. So the answer is `OR(all elements) << (n - 1)` — OR everything together, then multiply by 2ⁿ⁻¹.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can move past brute-forcing 2ⁿ subsets to a per-bit counting argument, and justify the 'exactly half the subsets' claim.

Where candidates slip

Brute-forcing all subsets (fine for small n but exponential), or miscounting how many subsets set a given bit and using 2ⁿ instead of 2ⁿ⁻¹.

How to stand out

Derive that a bit is set in half of all subset XORs, conclude the answer is OR × 2ⁿ⁻¹, and explain why the empty subset is harmless.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate All Subsets	`O(2ⁿ · n)`	`O(1)`	State it first to show you understand the definition, then say 'this is exponential; we can collapse it'.	Read
2	Per-Bit Counting — OR × 2ⁿ⁻¹ (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'each bit in the OR shows up in exactly half the subset XORs'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewSum XOR over all subsetsIs n small enough for 2ⁿ?Just show itWant O(n)Explore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate All Subsets

TimeO(2ⁿ · n)SpaceO(1)

State it first to show you understand the definition, then say 'this is exponential; we can collapse it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How many subsets are there, and how do you compute the XOR total of one subset?

2Hint 2Explore hint

Use a bitmask from 0 to 2ⁿ - 1; bit j of the mask means 'include nums[j]'. XOR the chosen elements.

3Hint 3Explore hint

Accumulate each subset's XOR into a running sum. The empty mask contributes 0 automatically.

A · Core idea

Translate the definition directly into code by walking every subset.

Encode subsets as bitmasks. A mask from 0 to 2ⁿ - 1 represents a subset: if bit j is set, include nums[j]. Mask 0 is the empty subset; the all-ones mask is the full array.

XOR the chosen elements. For each mask, scan its set bits and XOR the corresponding values into a subset total. Add that total to the grand sum.

Why this is the honest baseline. It mirrors the problem statement one-to-one and is correct for any n. With n ≤ 12 it even passes. But it does exponential work, and the interviewer wants you to notice the structure that makes it collapse.

Where it breaks down. At larger n, 2ⁿ is hopeless. That pressure is the cue to analyze bits independently instead of enumerating subsets.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 3]

Array state

00,01

0, 1

[0]

mask ↓

[1]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

Reference implementation previewpublic int subsetXORSum(int[] nums) { int n = nums.length; int sum = 0; for (int mask = 0; mask < (1 << n); mask++) { int xor = 0;Explore the full code

solution.javaJava

Brute Force — Enumerate All Subsets — reference

3 teaching notes

1
public int subsetXORSum(int[] nums) {
2
    int n = nums.length;
3
    int sum = 0;
4
    // Enumerate all 2ⁿ subsets as bitmasks.
5
    for (int mask = 0; mask < (1 << n); mask++) {
6
        int xor = 0;
7
        for (int j = 0; j < n; j++) {
8
            // Bit j of the mask decides whether nums[j] is in this subset.
9
            if ((mask & (1 << j)) != 0) {
10
                xor ^= nums[j];
11
            }
12
        }
13
        // Accumulate each subset's XOR total into the grand sum.
14
        sum += xor;
15
    }
16
    return sum;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(2ⁿ · n) timeO(1) spaceOpen the invariant and proofExplore the proof

Enumerating subsets re-derives the same bit interactions over and over. The moment you ask 'how often is bit b set across all these XORs?' you stop enumerating and start counting — the path to the linear solution.

ComplexityO(2ⁿ · n) time, O(1) space — There are 2ⁿ masks; building each subset's XOR scans up to n bits, so O(2ⁿ · n). Only a running total is stored, so O(1) extra space.

E · Edge cases and pitfalls3Starting the mask loop at 1 and silently dropping the (harmless) empty subset — fine here but a habit worth noting.Explore edge cases

Pitfalls

Starting the mask loop at 1 and silently dropping the (harmless) empty subset — fine here but a habit worth noting.
Resetting xor outside the mask loop, leaking one subset's value into the next.
Assuming this scales — it's exponential and only acceptable for tiny n.

03.2

Approach 2 of 2 · Optimal

Per-Bit Counting — OR × 2ⁿ⁻¹ (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'each bit in the OR shows up in exactly half the subset XORs'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at one bit position b in isolation. When is that bit set in a subset's XOR total?

2Hint 2Explore hint

Bit b is 1 in a subset's XOR iff the subset contains an odd number of elements that have bit b set. If no element has bit b, it's never set.

3Hint 3Explore hint

If at least one element has bit b, exactly half of all 2ⁿ subsets have an odd count of those elements. So bit b contributes 2^b × 2ⁿ⁻¹. Sum over bits = OR × 2ⁿ⁻¹.

A · Core idea

Decompose the sum bit by bit, because XOR acts on each bit independently.

Fix one bit position b. A subset's XOR total has bit b set exactly when the subset contains an odd number of elements whose bit b is 1. Bits are independent under XOR, so we can total each bit's contribution separately and add them up.

Case 1: no element has bit b. Then no subset can ever set bit b in its XOR — bit b contributes 0 to every subset. Notice 'some element has bit b' is precisely 'the OR of all elements has bit b'.

Case 2: at least one element has bit b. Say k ≥ 1 elements have bit b set. A subset sets bit b iff it picks an odd number of those k elements. The number of ways to pick an odd-sized subset from k items is 2^{k-1}, and the remaining n - k elements are each free (in or out), giving 2^{n-k} choices. So the count of subsets that set bit b is 2^{k-1} × 2^{n-k} = 2^{n-1} — exactly half of all 2ⁿ subsets, independent of k.

Combine. Each bit present in the OR contributes 2^b to 2^{n-1} subsets, i.e. 2^b × 2^{n-1}. Summing over all set bits of the OR factors out the 2^{n-1}: the answer is OR(all elements) × 2^{n-1}, which is just OR << (n - 1). The empty subset contributes 0 and is already accounted for in the half-count.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5, 1, 6]

Array state

101

bit ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result28

C · Code with teaching comments

solution.javaJava

Per-Bit Counting — OR × 2ⁿ⁻¹ (Optimal) — optimal

2 teaching notes

1
public int subsetXORSum(int[] nums) {
2
    int orAll = 0;
3
    for (int x : nums) {
4
        // OR collects every bit that any element sets — these are exactly the
5
        // achievable bits.
6
        orAll |= x;
7
    }
8
    // Each achievable bit appears in 2ⁿ⁻¹ subset XORs, so multiply the OR by 2ⁿ⁻¹ via a
9
    // left shift.
10
    return orAll << (nums.length - 1);
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole exponential sum collapses because 'how many subsets set this bit?' has the same answer — half — for every bit that's achievable at all. Once a single element carries a bit, the parity of all the others splits the subsets evenly, so 2ⁿ⁻¹ is universal and the OR captures exactly which bits are achievable.

ComplexityO(n) time, O(1) space — ORing all n elements is a single O(n) pass; one shift gives ×2ⁿ⁻¹. Constant extra space. This is optimal — you must read every element at least once.

E · Edge cases and pitfalls7nums = [n] (single element a) — OR = a, n - 1 = 0, a << 0 = a; matches {} + {a} = a.Explore edge cases

Edge cases handled

nums = [n] (single element a)OR = a, n - 1 = 0, a << 0 = a; matches {} + {a} = a.
all elements equal, e.g. [4, 4]OR = 4, n = 2, 4 << 1 = 8; subsets {},{4},{4},{4,4=0} → 0+4+4+0 = 8.
elements share no bits, e.g. [1, 2, 4]OR = 7, n = 3, 7 << 2 = 28.
large n with shiftn - 1 up to 11 here; the shift stays within int range given the small values.

Pitfalls

Multiplying by 2ⁿ instead of 2ⁿ⁻¹ — double-counts; only half the subsets set each bit.
Shifting by n instead of n - 1 — same off-by-one error.
Trying to sum element values instead of OR-ing them — addition double-counts shared bits.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int subsetXORSum(int[] nums) { int orAll = 0; for (int x : nums) { orAll |= x; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong multiplier (2ⁿ vs 2ⁿ⁻¹)

Only half of the 2ⁿ subsets have an odd count of elements carrying a given bit, so each bit is set in 2ⁿ⁻¹ subsets, not 2ⁿ.

Explore the code comparison

Don't write this

return or_all << len(nums)        # 2^n — doubles the real answer

Write this instead

return or_all << (len(nums) - 1)  # 2^(n-1) — correct half

Summing instead of OR-ing

Adding values double-counts bits shared by multiple elements; only the OR captures the set of achievable bits without inflation.

Explore the code comparison

Don't write this

int s = 0;
for (int x : nums) s += x;        // wrong: sums, not OR
return s << (nums.length - 1);

Write this instead

int orAll = 0;
for (int x : nums) orAll |= x;     // OR collects achievable bits
return orAll << (nums.length - 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Per-bit contribution counting → OR of all values times 2ⁿ⁻¹

Code pattern to memorize

answer = (a[0] | a[1] | ... | a[n-1]) * 2^(n-1)
# each set bit of the OR appears in exactly half of all subset XORs

Rules to remember

1A bit can appear in any subset XOR only if some element has that bit set — that's exactly the OR.
2If a bit is present in the OR, it is set in the XOR of exactly half (2ⁿ⁻¹) of all subsets.
3So each OR bit contributes 2^bit × 2ⁿ⁻¹; summed over bits that's OR << (n - 1).
4The empty subset contributes 0 (XOR of nothing) — it doesn't change the total.
5For n = 1 the formula gives OR × 2⁰ = the single element itself, which matches {} + {a} = a.

Use this pattern when

Summing or counting a bitwise quantity across all subsets
Any 'over all subsets, total of XOR/AND/OR' aggregation
Problems where per-bit independence collapses an exponential sum to linear
Recognizing 'half the subsets flip a given bit' parity arguments

Choose another pattern when

Need the actual subsets, not an aggregate → enumerate, you can't avoid 2ⁿ
Sum of subset *products* or non-bitwise functions → per-bit trick doesn't apply
Maximum subset XOR → linear-basis / trie, a different technique
n tiny and clarity matters most → brute force is acceptable

Interview takeaway

Subset XOR sum is a per-bit counting problem: every bit present in the OR is set in half the subsets, so the answer is OR × 2ⁿ⁻¹. Decomposing a subset aggregate bit-by-bit is the move that turns 2ⁿ into O(n).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSubset XOR sum is a per-bit counting problem: each bit present in the OR is set in exactly half of all subset XORs, giving OR × 2ⁿ⁻¹. Decomposing a subset aggregate bit-by-bit is the reusable trick.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Subset XOR Sum via DFS
Coming soon
If asked to enumerate, a recursive include/exclude DFS accumulates the same total in O(2ⁿ).
Subsets
Coming soon
The enumeration backbone — bitmask or backtracking to list all 2ⁿ subsets.
Maximum XOR With an Element From Array
Coming soon
Maximizing XOR uses a binary trie / linear basis, not per-bit counting.
Bitwise ORs of Subarrays
Coming soon
Another subset/subarray bit-aggregation, solved by tracking the frontier of distinct ORs.

Same pattern

←

Sum Over Subsets (SOS DP)

Continue · Next problem

Flipping Bits

mediumBit ManipulationLC #1863Sometimes asked

Sum of All Subset XOR Totals

LCPractice

Bit Manipulation · 12 of 20 · 10 min

The XOR total of an array is the bitwise XOR of all its elements; the XOR total of an empty array is 0.

Given an array nums, return the sum of the XOR totals of every subset of nums. Subsets with the same elements but different indices are counted separately.

In plain English

Examples

Example 1

Input: nums = [1, 3]
Output: 6
Note: Subsets: {}→0, {1}→1, {3}→3, {1,3}→2. Sum = 0+1+3+2 = 6. Check: OR(1,3)=3, ×2¹ = 6.

Example 2

Input: nums = [5, 1, 6]
Output: 28
Note: OR(5,1,6) = 7, n = 3, so 7 × 2² = 28.

Example 3

Input: nums = [3, 4, 5, 6, 7, 8]
Output: 480
Note: OR of all = 15, n = 6, so 15 × 2⁵ = 15 × 32 = 480.

Constraints

1 ≤ nums.length ≤ 12
1 ≤ nums[i] ≤ 20
There are 2ⁿ subsets, including the empty subset

Clarifying questions4First question: Is the empty subset included?Explore questions

Q1.Is the empty subset included?
Yes, but its XOR total is 0, so it adds nothing. Including or excluding it gives the same sum.
Q2.Are subsets distinguished by index or by value?
By index — duplicate values at different positions form distinct subsets. The counting argument naturally treats each element independently.
Q3.How large is n?
Up to 12 here, so even 2ⁿ ≈ 4096 brute force is fine. I'll show it, then give the O(n) closed form.
Q4.Can values be 0 or negative?
Values are positive per constraints. The bit argument would still hold for 0; negatives would need care with the sign bit, but that's out of scope here.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can move past brute-forcing 2ⁿ subsets to a per-bit counting argument, and justify the 'exactly half the subsets' claim.

Where candidates slip

Brute-forcing all subsets (fine for small n but exponential), or miscounting how many subsets set a given bit and using 2ⁿ instead of 2ⁿ⁻¹.

How to stand out

Derive that a bit is set in half of all subset XORs, conclude the answer is OR × 2ⁿ⁻¹, and explain why the empty subset is harmless.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Enumerate All Subsets	`O(2ⁿ · n)`	`O(1)`	State it first to show you understand the definition, then say 'this is exponential; we can collapse it'.	Read
2	Per-Bit Counting — OR × 2ⁿ⁻¹ (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Phrase it as 'each bit in the OR shows up in exactly half the subset XORs'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Enumerate All Subsets

TimeO(2ⁿ · n)SpaceO(1)

State it first to show you understand the definition, then say 'this is exponential; we can collapse it'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How many subsets are there, and how do you compute the XOR total of one subset?

2Hint 2Explore hint

Use a bitmask from 0 to 2ⁿ - 1; bit j of the mask means 'include nums[j]'. XOR the chosen elements.

3Hint 3Explore hint

Accumulate each subset's XOR into a running sum. The empty mask contributes 0 automatically.

A · Core idea

Translate the definition directly into code by walking every subset.

Encode subsets as bitmasks. A mask from 0 to 2ⁿ - 1 represents a subset: if bit j is set, include nums[j]. Mask 0 is the empty subset; the all-ones mask is the full array.

XOR the chosen elements. For each mask, scan its set bits and XOR the corresponding values into a subset total. Add that total to the grand sum.

Where it breaks down. At larger n, 2ⁿ is hopeless. That pressure is the cue to analyze bits independently instead of enumerating subsets.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 3]

Array state

00,01

0, 1

[0]

mask ↓

[1]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

Reference implementation previewpublic int subsetXORSum(int[] nums) { int n = nums.length; int sum = 0; for (int mask = 0; mask < (1 << n); mask++) { int xor = 0;Explore the full code

solution.javaJava

Brute Force — Enumerate All Subsets — reference

3 teaching notes

1
public int subsetXORSum(int[] nums) {
2
    int n = nums.length;
3
    int sum = 0;
4
    // Enumerate all 2ⁿ subsets as bitmasks.
5
    for (int mask = 0; mask < (1 << n); mask++) {
6
        int xor = 0;
7
        for (int j = 0; j < n; j++) {
8
            // Bit j of the mask decides whether nums[j] is in this subset.
9
            if ((mask & (1 << j)) != 0) {
10
                xor ^= nums[j];
11
            }
12
        }
13
        // Accumulate each subset's XOR total into the grand sum.
14
        sum += xor;
15
    }
16
    return sum;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(2ⁿ · n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(2ⁿ · n) time, O(1) space — There are 2ⁿ masks; building each subset's XOR scans up to n bits, so O(2ⁿ · n). Only a running total is stored, so O(1) extra space.

E · Edge cases and pitfalls3Starting the mask loop at 1 and silently dropping the (harmless) empty subset — fine here but a habit worth noting.Explore edge cases

Pitfalls

Starting the mask loop at 1 and silently dropping the (harmless) empty subset — fine here but a habit worth noting.
Resetting xor outside the mask loop, leaking one subset's value into the next.
Assuming this scales — it's exponential and only acceptable for tiny n.

03.2

Approach 2 of 2 · Optimal

Per-Bit Counting — OR × 2ⁿ⁻¹ (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Phrase it as 'each bit in the OR shows up in exactly half the subset XORs'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at one bit position b in isolation. When is that bit set in a subset's XOR total?

2Hint 2Explore hint

Bit b is 1 in a subset's XOR iff the subset contains an odd number of elements that have bit b set. If no element has bit b, it's never set.

3Hint 3Explore hint

If at least one element has bit b, exactly half of all 2ⁿ subsets have an odd count of those elements. So bit b contributes 2^b × 2ⁿ⁻¹. Sum over bits = OR × 2ⁿ⁻¹.

A · Core idea

Decompose the sum bit by bit, because XOR acts on each bit independently.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5, 1, 6]

Array state

101

bit ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result28

C · Code with teaching comments

solution.javaJava

Per-Bit Counting — OR × 2ⁿ⁻¹ (Optimal) — optimal

2 teaching notes

1
public int subsetXORSum(int[] nums) {
2
    int orAll = 0;
3
    for (int x : nums) {
4
        // OR collects every bit that any element sets — these are exactly the
5
        // achievable bits.
6
        orAll |= x;
7
    }
8
    // Each achievable bit appears in 2ⁿ⁻¹ subset XORs, so multiply the OR by 2ⁿ⁻¹ via a
9
    // left shift.
10
    return orAll << (nums.length - 1);
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — ORing all n elements is a single O(n) pass; one shift gives ×2ⁿ⁻¹. Constant extra space. This is optimal — you must read every element at least once.

E · Edge cases and pitfalls7nums = [n] (single element a) — OR = a, n - 1 = 0, a << 0 = a; matches {} + {a} = a.Explore edge cases

Edge cases handled

nums = [n] (single element a)OR = a, n - 1 = 0, a << 0 = a; matches {} + {a} = a.
all elements equal, e.g. [4, 4]OR = 4, n = 2, 4 << 1 = 8; subsets {},{4},{4},{4,4=0} → 0+4+4+0 = 8.
elements share no bits, e.g. [1, 2, 4]OR = 7, n = 3, 7 << 2 = 28.
large n with shiftn - 1 up to 11 here; the shift stays within int range given the small values.

Pitfalls

Multiplying by 2ⁿ instead of 2ⁿ⁻¹ — double-counts; only half the subsets set each bit.
Shifting by n instead of n - 1 — same off-by-one error.
Trying to sum element values instead of OR-ing them — addition double-counts shared bits.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int subsetXORSum(int[] nums) { int orAll = 0; for (int x : nums) { orAll |= x; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong multiplier (2ⁿ vs 2ⁿ⁻¹)

Only half of the 2ⁿ subsets have an odd count of elements carrying a given bit, so each bit is set in 2ⁿ⁻¹ subsets, not 2ⁿ.

Explore the code comparison

Don't write this

return or_all << len(nums)        # 2^n — doubles the real answer

Write this instead

return or_all << (len(nums) - 1)  # 2^(n-1) — correct half

Summing instead of OR-ing

Adding values double-counts bits shared by multiple elements; only the OR captures the set of achievable bits without inflation.

Explore the code comparison

Don't write this

int s = 0;
for (int x : nums) s += x;        // wrong: sums, not OR
return s << (nums.length - 1);

Write this instead

int orAll = 0;
for (int x : nums) orAll |= x;     // OR collects achievable bits
return orAll << (nums.length - 1);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Per-bit contribution counting → OR of all values times 2ⁿ⁻¹

Code pattern to memorize

answer = (a[0] | a[1] | ... | a[n-1]) * 2^(n-1)
# each set bit of the OR appears in exactly half of all subset XORs

Rules to remember

1A bit can appear in any subset XOR only if some element has that bit set — that's exactly the OR.
2If a bit is present in the OR, it is set in the XOR of exactly half (2ⁿ⁻¹) of all subsets.
3So each OR bit contributes 2^bit × 2ⁿ⁻¹; summed over bits that's OR << (n - 1).
4The empty subset contributes 0 (XOR of nothing) — it doesn't change the total.
5For n = 1 the formula gives OR × 2⁰ = the single element itself, which matches {} + {a} = a.

Use this pattern when

Summing or counting a bitwise quantity across all subsets
Any 'over all subsets, total of XOR/AND/OR' aggregation
Problems where per-bit independence collapses an exponential sum to linear
Recognizing 'half the subsets flip a given bit' parity arguments

Choose another pattern when

Need the actual subsets, not an aggregate → enumerate, you can't avoid 2ⁿ
Sum of subset *products* or non-bitwise functions → per-bit trick doesn't apply
Maximum subset XOR → linear-basis / trie, a different technique
n tiny and clarity matters most → brute force is acceptable

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Subset XOR Sum via DFS
Coming soon
If asked to enumerate, a recursive include/exclude DFS accumulates the same total in O(2ⁿ).
Subsets
Coming soon
The enumeration backbone — bitmask or backtracking to list all 2ⁿ subsets.
Maximum XOR With an Element From Array
Coming soon
Maximizing XOR uses a binary trie / linear basis, not per-bit counting.
Bitwise ORs of Subarrays
Coming soon
Another subset/subarray bit-aggregation, solved by tracking the frontier of distinct ORs.

Same pattern

←

Sum Over Subsets (SOS DP)

Continue · Next problem

Flipping Bits