 # Total Hamming Distance

## 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;
arr=3;
arr=10;
arr=5;
arr=25;
arr=2;
arr=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

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.