Sum of All Subsets XOR Total

EASY✓ CHIP-TIMEDLC #1863 — FULL STATEMENT ↗

The drill: Every subset of an array has an XOR total — XOR all its members together, with the empty subset totaling 0. Add that XOR total up across every possible subset of the array.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An integer array shows up, and every one of its subsets — including the empty one — carries its own XOR total: XOR every member together, or 0 when there's nothing to XOR.

The task is to add up that XOR total across every single subset the array has, empty subset included, and hand back the grand total as one number.

Duplicate values are allowed and don't collapse into each other — two equal numbers still count as two separate elements when subsets are formed, so a value can appear twice within the same subset.

EX 01

nums = [1, 3]

→ 6

MINIMUM SIZE TWO

EX 02

nums = [7]

→ 7

SINGLE ELEMENT — ONLY SUBSET BESIDES EMPTY

EX 03

nums = [5, 1, 6]

→ 28

THREE DISTINCT VALUES

arrays typically stay small — under twenty or so elements, since subset count grows exponentially
values are non-negative integers
duplicate values are treated as distinct elements
the empty subset counts and contributes 0 to the total

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Brute force lists every subset and XORs it out, but that throws away a pattern — trace what happens to a single bit position across all subsets instead of one subset at a time.

HINT 2 THE STRUCTURE

Fix one bit. Across all 2ⁿ subsets, that bit ends up set in exactly half of them, but only for bits that appear in at least one number — pairing a subset with the same subset plus one extra qualifying element flips that bit's parity every time.

HINT 3 ONE STEP FROM THE ANSWER

The sum only needs the bitwise OR of the whole array. A bit present in the OR contributes 2ⁿ⁻¹ to the total, so the answer is (OR of all numbers) shifted left by n − 1.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE OR-AND-SHIFT SHORTCUTPATTERN · OR TIMES HALF THE SUBSETSnums = [5, 1, 6]

RUNNING OR

running OR → 0 (000)

STEP 1

Three numbers: 5, 1, 6. The trick skips walking every subset — it only ever tracks the bitwise OR of all of them.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/sum-of-all-subset-xor-totals.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        or_all = 0
        for v in nums:
            or_all |= v
        return or_all << (len(nums) - 1)

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 6 LN

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        for mask in range(1 << n):          # every one of the 2^n subsets...
            x = 0
            for i in range(n):
                if mask & (1 << i):
                    x ^= nums[i]
            total += x                       # ...decoded and XORed from scratch
        return total

TIME O(N·2ⁿ)SPACE O(N)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public int subsetXORSum(int[] nums) {
        int orAll = 0;
        for (int v : nums) {
            orAll |= v;
        }
        return orAll << (nums.length - 1);
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 9 LN

class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int total = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            int x = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    x ^= nums[i];
                }
            }
            total += x;
        }
        return total;
    }
}

TIME O(N·2ⁿ)SPACE O(N)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED