LC-1863 Easy LeetCode

1863. Sum of All Subset XOR Totals

Array Math Backtracking Bit Manipulation Combinatorics Enumeration

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 90% Topics: Array, Math, Backtracking, Bit Manipulation, Combinatorics, Enumeration

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def subsetXORSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # given there are k (k >= 1) nums of which ith bit is 1,
        # the bit contributes to sum is:
        # (nCr(k, 1) + nCr(k, 3) + ...) * (nCr(n - k, 0) + nCr(n - k, 1) + ...) * 2^i
        # = 2^(k-1) * 2^(n-k) = 2^(n-1) * 2^i
        result = 0
        for x in nums:
            result |= x
        return result * 2**(len(nums)-1)

Solution from kamyu104/LeetCode-Solutions · MIT