Medium · Bitmask Enumeration
Understand → Visualise → Practice.
Return the sum of XOR values over all subsets, including the empty subset.
A bit that is set in any element is set in exactly half of all 2ⁿ subset XORs, so the total equals (OR of all values) × 2ⁿ⁻¹.
Enumerating all 2ⁿ subsets with a bitmask and XOR-ing each one is correct but exponential.
OR all values together: only bits set somewhere can appear in a subset XOR.
Each such bit is set in 2ⁿ⁻¹ subsets, so return OR × 2ⁿ⁻¹ (and 0 for an empty array).
O(n) time and O(1) space with the contribution formula; O(n·2ⁿ) by enumeration.
The empty subset counts and contributes XOR 0, so don't skip it or treat it as an error.
Read the full guide first: Bit Manipulation and Bitmask Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.