1863. Sum of All Subset XOR Totals

Description

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

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

Solutions

Solution 1: Binary Enumeration

We can use binary enumeration to enumerate all subsets, and then calculate the XOR sum of each subset.

Specifically, we enumerate \(i\) in the range \([0, 2^n)\), where \(n\) is the length of the array \(nums\). If the \(j\)th bit of the binary representation of \(i\) is \(1\), it means that the \(j\)th element of \(nums\) is in the current subset; if the \(j\)th bit is \(0\), it means that the \(j\)th element of \(nums\) is not in the current subset. We can get the XOR sum of the current subset according to the binary representation of \(i\), and add it to the answer.

The time complexity is \(O(n \times 2^n)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(1 << n):
            s = 0
            for j in range(n):
                if i >> j & 1:
                    s ^= nums[j]
            ans += s
        return ans

class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < 1 << n; ++i) {
            int s = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    s ^= nums[j];
                }
            }
            ans += s;
        }
        return ans;
    }
}

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < 1 << n; ++i) {
            int s = 0;
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1) {
                    s ^= nums[j];
                }
            }
            ans += s;
        }
        return ans;
    }
};

func subsetXORSum(nums []int) (ans int) {
    n := len(nums)
    for i := 0; i < 1<<n; i++ {
        s := 0
        for j, x := range nums {
            if i>>j&1 == 1 {
                s ^= x
            }
        }
        ans += s
    }
    return
}

function subsetXORSum(nums: number[]): number {
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i < 1 << n; ++i) {
        let s = 0;
        for (let j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                s ^= nums[j];
            }
        }
        ans += s;
    }
    return ans;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var subsetXORSum = function (nums) {
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i < 1 << n; ++i) {
        let s = 0;
        for (let j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                s ^= nums[j];
            }
        }
        ans += s;
    }
    return ans;
};

Solution 2: DFS (Depth-First Search)

We can also use depth-first search to enumerate all subsets, and then calculate the XOR sum of each subset.

We design a function \(dfs(i, s)\), where \(i\) represents the current search to the \(i\)th element of the array \(nums\), and \(s\) represents the XOR sum of the current subset. Initially, \(i=0\), \(s=0\). During the search, we have two choices each time:

Add the \(i\)th element of \(nums\) to the current subset, i.e., \(dfs(i+1, s \oplus nums[i])\);
Do not add the \(i\)th element of \(nums\) to the current subset, i.e., \(dfs(i+1, s)\).

When we have searched all elements of the array \(nums\), i.e., \(i=n\), the XOR sum of the current subset is \(s\), and we can add it to the answer.

The time complexity is \(O(2^n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(nums\).