Sponsored
Sponsored
This 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.
Time Complexity: O(2n), where n is the length of nums.
Space Complexity: O(n) because of the recursion stack.
1#include <stdio.h>
2
3void xorSubsetSum(int *nums, int size, int index, int currentXor, int *result) {
4 if (index == size) {
5 *result += currentXor;
6 return;
7 }
8 xorSubsetSum(nums, size, index + 1, currentXor, result);
9 xorSubsetSum(nums, size, index + 1, currentXor ^ nums[index], result);
10}
11
12int subsetXORSum(int* nums, int numsSize) {
13 int result = 0;
14 xorSubsetSum(nums, numsSize, 0, 0, &result);
15 return result;
16}
17
18int main() {
19 int nums[] = {1, 3};
20 int result = subsetXORSum(nums, 2);
21 printf("%d\n", result); // Output: 6
22 return 0;
23}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.
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.
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.
1
class Program {
static void Main() {
int[] nums = {1, 3};
Console.WriteLine(SubsetXorSum(nums)); // Output: 6
}
public static int SubsetXorSum(int[] nums) {
int totalXOR = 0;
int totalSubsets = 1 << nums.Length;
for (int mask = 0; mask < totalSubsets; mask++) {
int currentXOR = 0;
for (int i = 0; i < nums.Length; i++) {
if ((mask & (1 << i)) != 0) {
currentXOR ^= nums[i];
}
}
totalXOR += currentXOR;
}
return totalXOR;
}
}This C# solution generates subsets using bit manipulation and accumulates their XOR into the total. Each bit in mask determines whether an element participates in the current subset's XOR calculation.