Sum of All Subset XOR Totals
Sum of All Subset XOR Totals is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Subsets (Include/Exclude) subpattern.
Problem statement
nums contains integers, and a subset is formed by choosing any collection of its elements, while preserving no ordering requirement. Each element may be chosen at most once, and the empty subset is allowed.
The XOR total of a subset is the bitwise XOR of all values in that subset. The XOR total of the empty subset is 0.
Implement Solution.subsetXORSum(nums) and return the sum of the XOR totals of every possible subset of nums, including the empty subset.
Example 1:
Input: nums = [1,2,4] Output: 28 Explanation: The eight subset XOR totals sum to 28; the empty subset contributes 0.
Example 2:
Input: nums = [0,5,0] Output: 20 Explanation: Exactly four subsets have XOR total 5, while the others have total 0, giving 4 5 = 20.
Example 3:
Input: nums = [6] Output: 6 Explanation: The empty subset contributes 0 and the subset containing 6 contributes 6.
Constraints:
- 1 <= nums.length <= 12 - 0 <= nums[i] <= 10^4 - nums contains only integers - Every position in nums represents a distinct selectable occurrence, even when values are equal
Topics and companies
Topics: Array, Backtracking, Bit Manipulation, Recursion.
How to practise Sum of All Subset XOR Totals on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Sum of All Subset XOR Totals in the code editor, or read the Sum of All Subset XOR Totals editorial for a worked solution with its approach and complexity analysis.
Where Sum of All Subset XOR Totals sits in the DSA pattern sheet
- Backtracking Patterns pattern guide
- Subsets (Include/Exclude) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Sum of All Subset XOR Totals
Other problems that use the same Subsets (Include/Exclude) and Backtracking Patterns techniques:
- Combinations — Medium, same subpattern
- Letter Combinations of a Phone Number — Medium, same subpattern
- Subsets — Medium, same subpattern
- Subsets II — Medium, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combination Sum — Medium, same pattern