The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.
[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 <= 121 <= nums[i] <= 20This approach uses recursion to generate all possible subsets of the array and calculates their XOR sum. The function will explore each element, either including or excluding it in the subset. This will give us the XOR sum for each subset, and we can accumulate the total from there.
This C program recursively calculates the XOR total of all subsets of given array nums. It calls xorSubsetSum either including or excluding the current number, and accumulates the XOR total in result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2n), where n is the length of nums.
Space Complexity: O(n) because of the recursion stack.
The alternative approach involves using bit manipulation to generate subsets efficiently. Each number's inclusion in a subset corresponds to a binary decision, allowing us to loop from 0 to (2n - 1) integers, using each binary representation as a decision for a subset.
This C solution calculates the XOR total by iterating over all possible subset representations using bitmasks. Each bit in mask represents the inclusion or exclusion of an element.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * 2n), where n is the length of nums due to the bitwise operations.
Space Complexity: O(1) as no additional space is used apart from counters.
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Subset Generation | Time Complexity: O(2n), where n is the length of nums. |
| Approach 2: Bitwise Combination | Time Complexity: O(n * 2n), where n is the length of nums due to the bitwise operations. |
Sum of All Subsets XOR Total - Leetcode 1863 - Python • NeetCodeIO • 14,573 views views
Watch 9 more video solutions →Practice Sum of All Subset XOR Totals with our built-in code editor and test cases.
Practice on FleetCode