Total Hamming Distance — Bit Position Analysis
Sanjeev SharmaAdvertisement
Problem
Find sum of Hamming distances between all pairs of numbers.
Approach
For each of the 32 bit positions, count ones and zeros among all numbers. Pairs with differing bits = ones * zeros.
Time: O(32*n) = O(n) | Space: O(1)
Solutions
Python
class Solution:
def totalHammingDistance(self, nums: list[int]) -> int:
total=0; n=len(nums)
for bit in range(32):
ones=sum((x>>bit)&1 for x in nums)
total+=ones*(n-ones)
return total
C++
class Solution {
public:
int totalHammingDistance(vector<int>& nums){
int n=nums.size(),total=0;
for(int b=0;b<32;b++){
int ones=0; for(int x:nums) ones+=(x>>b)&1;
total+=ones*(n-ones);
}
return total;
}
};
Complexity
- Time: O(n * 32) = O(n) | Space: O(1)
Advertisement
