1863. Sum of All Subset XOR Totals

NeetCode: Sum of All Subset XOR Totals · LeetCode: 1863. Sum of All Subset XOR Totals · Difficulty: Easy

The XOR total of an array is the bitwise XOR of all its elements, or 0 if the array is empty. Given an array nums, return the sum of the XOR totals of every subset of nums. Subsets that have the same elements but come from different index choices are counted separately.

Example

Input:  nums = [1,3]      Output: 6      // subsets: [] = 0, [1] = 1, [3] = 3, [1,3] = 2
Input:  nums = [5,1,6]    Output: 28

Brute force: enumerate every subset with a bitmask

Each number from 0 to 2^n - 1 describes one subset: bit i says whether nums[i] is included. XOR the chosen elements and add up the totals. LeetCode's Java signature is int subsetXORSum(int[] nums). ^ is Java's bitwise XOR operator.

public class Main {
    static 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 >> i & 1) == 1) {
                        x ^= nums[i];
                    }
                }
                total += x;
            }
            return total;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.subsetXORSum(new int[] {1, 3}));
        System.out.println(s.subsetXORSum(new int[] {5, 1, 6}));
        System.out.println(s.subsetXORSum(new int[] {3, 4, 5, 6, 7, 8}));
    }
}

6
28
480

There are 2^n subsets and each costs O(n) to XOR. Time: O(n * 2^n). Space: O(1).

Optimal: OR of everything, shifted left by n - 1

Consider one bit position at a time. If no number has that bit set, it contributes nothing to any subset. If at least one number has it set, exactly half of all subsets (2^(n-1) of them) have that bit set in their XOR: pairing each subset with the same subset toggled on one fixed number that owns the bit flips the parity, so subsets of odd and even parity are equally many.

Every bit that appears anywhere therefore contributes bit * 2^(n-1) to the total. The bits that appear anywhere are exactly those of the OR of all elements, giving (OR of nums) * 2^(n-1). The constraints guarantee n >= 1.

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

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.subsetXORSum(new int[] {1, 3}));
        System.out.println(s.subsetXORSum(new int[] {5, 1, 6}));
        System.out.println(s.subsetXORSum(new int[] {3, 4, 5, 6, 7, 8}));
    }
}

6
28
480

For [1, 3] the OR is 3 and 3 << 1 = 6, which matches. The result fits in int because nums[i] <= 20 and n <= 12; int shifts silently drop bits that move past bit 31, so larger inputs would need long. Time: O(n). Space: O(1).