Leetcode 0477 Total Hamming Distance

Problem statement

https://leetcode.com/problems/total-hamming-distance/

Solution

Go bit by bit and let m_i be number of zeros for i-th bit and n_i be number of ones for i-th bit. Then we need to add m_i * n_i to total hamming distance.

Complexity

Time complexity is O(32n), where n is number of numbers, space complexity is O(1).

Code

class Solution:
    def totalHammingDistance(self, nums):
        n, ans = len(nums), 0
        for i in range(32):
            s = sum(num >> i & 1 for num in nums)
            ans += s*(n-s)
        return ans