Sum of All Subset XOR Totals

Easy
439.

Sum of All Subset XOR Totals

Sum of All Subset XOR Totals is an easy coding problem on arrays, math and bit manipulation, asked in Amazon and Adobe interviews.

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

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

Example 1

Input
nums = [1,3]
Output
6
Explanation
The subsets give 0, 1, 3 and 2.

Example 2

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

Example 3

Input
nums = [3,4,5,6,7,8]
Output
480

Constraints

  • 1 <= nums.length <= 20
  • 1 <= nums[i] <= 20

Follow-up: Enumerating all 2^n subsets works for n ≤ 20. Can you find the closed form?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sum of All Subset XOR Totals — Problem & Solution

Sum of All Subset XOR Totals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Sum of All Subset XOR Totals is an easy coding problem on arrays, math and bit manipulation, asked in Amazon and Adobe interviews.

Problem statement

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

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

Example 1

Input: nums = [1,3]
Output: 6
Explanation: The subsets give 0, 1, 3 and 2.

Example 2

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

Example 3

Input: nums = [3,4,5,6,7,8]
Output: 480

Constraints

  • 1 <= nums.length <= 20
  • 1 <= nums[i] <= 20

Follow-up: Enumerating all 2^n subsets works for n ≤ 20. Can you find the closed form?

Hints for Sum of All Subset XOR Totals

  1. Hint 1

    Enumerating the 2^n subsets is fine here, but look at one bit position at a time.

  2. Hint 2

    If any element has a given bit set, exactly half of all subsets end up with that bit set in their XOR.

  3. Hint 3

    So the answer is (nums[0] | nums[1] | … ) * 2^(n-1).

How to solve Sum of All Subset XOR Totals

For each bit that appears in at least one element, exactly half of all subsets have that bit set in their XOR; the answer is (OR of all) · 2^(n-1).

Approach

  1. OR all elements.
  2. Shift left by n - 1.

Why it works

Fix an element with the bit set; pairing each subset with the one obtained by toggling that element's membership flips the XOR bit, so subsets split evenly. Bits present in no element contribute nothing.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Enumerating 2^n subsets is fine at this size but misses the point.

Reference solution

Python

def subsetXORSum(nums) -> int:
    or_all = 0
    for x in nums:
        or_all |= x
    return or_all << (len(nums) - 1)

Java

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

C++

int subsetXORSum(vector<int>& nums) {
    int orAll = 0;
    for (int x : nums) orAll |= x;
    return orAll << ((int) nums.size() - 1);
}

JavaScript

var subsetXORSum = function(nums) {
    let orAll = 0;
    for (let i = 0; i < nums.length; i++) orAll |= nums[i];
    return orAll * Math.pow(2, nums.length - 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation