1863. Sum of All Subset XOR Totals LeetCode Solution
In this guide, you will get 1863. Sum of All Subset XOR Totals LeetCode Solution with the best time and space complexity. The solution to Sum of All Subset XOR Totals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
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
Complexity Analysis
Time Complexity: O(2^n)
Space Complexity: O(2^n)
1863. Sum of All Subset XOR Totals LeetCode Solution in C++
class Solution {
public:
int subsetXORSum(vector<int>& nums) {
return dfs(nums, 0, 0);
}
private:
int dfs(const vector<int>& nums, int i, int xors) {
if (i == nums.size())
return xors;
const int x = dfs(nums, i + 1, xors);
const int y = dfs(nums, i + 1, nums[i] ^ xors);
return x + y;
}
}; /* code provided by PROGIEZ */
1863. Sum of All Subset XOR Totals LeetCode Solution in Java
class Solution {
public int subsetXORSum(int[] nums) {
return dfs(nums, 0, 0);
}
private int dfs(int[] nums, int i, int xors) {
if (i == nums.length)
return xors;
final int x = dfs(nums, i + 1, xors);
final int y = dfs(nums, i + 1, nums[i] ^ xors);
return x + y;
}
} // code provided by PROGIEZ
1863. Sum of All Subset XOR Totals LeetCode Solution in Python
class Solution:
def subsetXORSum(self, nums: list[int]) -> int:
def dfs(i: int, xors: int) -> int:
if i == len(nums):
return xors
x = dfs(i + 1, xors)
y = dfs(i + 1, nums[i] ^ xors)
return x + y
return dfs(0, 0) # code by PROGIEZ
