LeetCode - 1863. Sum of All Subset XOR Totals

Easy

這題用數論真香，推

1863. Sum of All Subset XOR Totals

題目

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

Example 3:

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

解題思路

bit manipulation (by Editorial)

可以觀察到，按照每個 subset 的加總，也就是把所有數字的 bit 做 or 後的結果，然後在右側補上 N-1 個 0

1	0	0	1
5	1	0	1
6	1	1	0
or	1	1	1
ans 28	1	1	1	0	0

Solution Code

class Solution(object):
    def subsetXORSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # bit manipulation (by Editorial)
        # 把所有數字的 bit 做 or 後的結果，然後在右側補上 N-1 個 0
        ans = 0
        N = len(nums)
        for i in range(N):
            ans = ans | nums[i]
        
        # decimal to binary
        bin(ans).replace("0b", "")

        # 右邊補 N-1 個 0，也就是往左移 N-1 個 bit
        ans = ans << N-1

        return ans