Problem Statement

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Example 1:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Example 2:

Input: nums = [4,14,4]
Output: 4

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

Problem Link

Total Hamming Distance - LeetCode

Approach

For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k*(n-k) hamming distance to the total.

Code

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        
        int n = nums.size();
        int res = 0;
        
        for(int i=0;i<32;i++)
        {
            int count = 0; //count of numbers having lsb as 1
            
            for(int num:nums)
            
                count+=((num>>i)&1);
                
                res+=(count)*(n-count);
            
        }
        
        return res;
        
    }
};