1863. Sum of All Subset XOR Totals

Array Math Bit Manipulation Backtracking enumeration

Time: O(n)

Space: O(1)

Intuition

Sum of XOR of all subsets. Each bit contributes 2^(n-1) to the total if any element has that bit set (since it appears in half of subsets with non-zero XOR).

Algorithm

1OR all elements together: bits_present.
2Answer = bits_present * 2^(n-1).

Common Pitfalls

•Each bit that appears in any element contributes 2^(n-1) to total XOR sum. Multiply OR by 2^(n-1).

1863.cs

// Approach: Math shortcut — OR all elements; result = OR * 2^(n-1) (each bit contributes equally).
// Time: O(n) Space: O(1)

public class Solution
{
    public int SubsetXORSum(int[] nums)
    {
        int n = nums.Length;
        int ans = 0;

        for (int i = 0; i < (1 << n); i++)
        {
            int subsetXOR = 0;
            for (int j = 0; j < n; j++)
            {
                if (((i >> j) & 1) != 0)
                    subsetXOR ^= nums[j];
            }
            ans += subsetXOR;
        }

        return ans;
    }
}

Was this solution helpful?