Total Hamming Distance

Companies:
  • Amazon Interview Questions

Problem Statement

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

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Sample Test Cases

Input: 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). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Problem Solution

 The fact that all numbers are represented using 32 bits (or some fixed number of bits). 

The idea is to count differences at individual bit positions. We traverse from 0 to 31 and count numbers with i’th bit set. 

Let this count be ‘count’. There would be “n-count” numbers with i’th bit not set. 

So count of differences at i’th bit would be “count * (n-count) * 2”, the reason for this formula is as every pair having one element which has set bit at i’th position and second element having unset bit at i’th position contributes exactly 1 to sum, therefore total permutation count will be count*(n-count) and multiply by 2 is due to one more repetition of all this type of pair as per given condition for making pair 1<=i,j<=N.

Like if array given {1,2,3,4,5}={ 001 , 010 , 011 , 100 , 101 }
so at 0th index, number of elements having set bit at 0th index is 3
And 2 elements having unset at 0th index.
So total hamming distance for i=0 will be 3 * 2=6
Same we can go for i=1,2,3,…31 and add all the distance and return final distance.

Complexity Analysis

Time Complexity: O(N) as we have to traverse the entire array.

Space Complexity: O(1) not using any data structure to store data.

Code Implementation

#include <bits/stdc++.h>
using namespace std;

 int totalHammingDistance(vector<int> nums) {
        int res=0;
        for(int i=0;i<32;i++)
        {
            int c=0;
            for(int j=0;j<nums.size();j++)
            {
                if((1<<i)&nums[j]) c++;  //checking ith bit set or not
            }
            res+=(nums.size()-c)*c;
        }
        return res;

    }

int main()
{

    vector<int>x;
    x.push_back(3);
    x.push_back(10);
    x.push_back(5);
    x.push_back(25);
    x.push_back(2);
    x.push_back(8);

    cout << totalHammingDistance(x)<< endl;

    return 0;
}

 

public class Hamming
{
    public int totalHammingDistance(int[] nums) 
    {
        int n = 31;
        int len = nums.length;
        int[] countOfOnes = new int[n];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < n; j++) {
                countOfOnes[j] += (nums[i] >> j) & 1;
            }
        }
        int sum = 0;
        for (int count: countOfOnes) {
            sum += count * (len - count);
        }
        return sum;
    }

    
    public static void main(String[] args) 
    {
        Hamming m = new Hamming();
        
        int arr[] = new int[6]; 
        arr[0]=3;
        arr[1]=10;
        arr[2]=5;
        arr[3]=25;
        arr[4]=2;
        arr[5]=8;
        
        System.out.println(m.totalHammingDistance(arr));
        
    }
}

 

def totalHammingDistance(nums):

        dist = 0
        
        for i in range(32):
            one_count = 0
            zero_count = 0
            
            for num in nums:
                bit = (1 << i) & num
                if bit == 0:
                    zero_count += 1
                else:
                    one_count += 1
                    
            dist += one_count * zero_count
            
        return dist
        
        
arr = [3,10,5,25,2,8]
print(totalHammingDistance(arr))

 

Scroll to Top