1.
Introduction
2.
Problem Statement
3.
Approach 1: Brute Force
3.1.
Algorithm
3.2.
Implementation
4.
Analysis of Complexity
4.1.
Time Complexity:
4.2.
Space Complexity:
5.
Approach 2: Bit Manipulation
5.1.
Implementation
6.
Analysis of Complexity
6.1.
Time Complexity
6.2.
Space Complexity
7.
8.
Key Takeaways
Last Updated: Mar 27, 2024

# Total Hamming Distance

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

One of the most exciting problems of the array and bit manipulation in leetcode and frequently asked in Google, Oracle. We will discuss this problem Pairwise Sum of Hamming Distance, Where we will be counting the Hamming distance between all pairs of the given numbers.

## Problem Statement

You are given an array of n elements. You have to return the hamming distances between all the pairs in the array.

Explanation of the problem

Input: arr[] = 5,10,4

Output: 8

Now understand this example, the binary representation of 5 is 0101,10 is 1010, and 4 is 0100. So the answer will be hamming(5,10) + hamming(10,4) + hamming(5,4)  = 4 + 3 + 1 = 8. Hence, the total Hamming distance is 8.

Note: We are taking four bits relevant in this case. The length of the array will not exceed 10^4.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach 1: Brute Force

Brute force is that approach that comes to your mind first, where you don't care about complexity. This approach will use the XOR operation(^), which compares two binary numbers bitwise. Here we will find xor of the pair, and with the use of '&,' we will compare the variable with the xor output if it is equal to one or not.

### Algorithm

1. Initialize a variable 'total' as 0 to store the total hamming distances of all the pairs.
2. Now traverse the given array by iterating from i = 0 to n. Now one more nested loop will iterate from j = i+1 to n.
3. We will take two variables and store the value of arr[i] in the first variable and arr[j] in the second variable.
4. We will store xor of these two variables in another variable, namely 'diff,' for future references.
5. Initialize another variable 'ret' as 1 to do '&' operation with diff.
6. Again with the help of a while loop which has a base containing till total>0. We will check if the '&' operation between ret and diff is greater than one or not. If not, then just right shift(>>) the diff variable by 1.
7. Total will be the final result.

### Implementation

``````public class Solution{

//function to calculate the hamming distance
public static int HammingDistance(int[] arr,n) {
int total=0;
//nested loops for checking each element side by side
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
//storing in variables to check one element with
//every other element.
int f1 = arr[i];
int f2 = arr[j];
//for storing the total result
total+=getDis(f1,f2);
}
}
}
public static int getDis(int f1,int f2){
//performing the xor operation
int diff = f1^f2;
int total= 0;
int ret= 1;

while(diff > 0){
if((ret & diff) == 1){
total++;
}
diff>>=1;
}
}

//main function
public static void main(String args[]){
int arr[]={5,10,4};
int n=3;
//printing the total distance
System.out.println(HammingDistance(arr,3));

}

}``````

OUTPUT :

``8``

Also see, Euclid GCD Algorithm

## Analysis of Complexity

### Time Complexity:

Here we are comparing each element in the array to each other using a nested loop finding the Hamming distance between each pair of elements. The overall worst-case complexity of comparing each element is O(32* n^2)~O(n^2).

### Space Complexity:

It will be O(1). No extra space was required.

## Approach 2: Bit Manipulation

What could be the efficient approach to solve this problem in O(n) complexity? It is that all the numbers are represented using 32 bits. We can separate the calculation to do one bit at a time.

Here we will be traversing from 0 to 31 and count numbers with i'th bit set. Let this count be 'ones.' There will be "arr. length - ones" numbers with i'th bit not set. So the count of differences at i'th bit would be "ones * (n-ones) * 2." the reason we are doing this is that in every pair, there will be one element that has set the bit at i'th position and a second element having an unset bit at i'th position which will result in 1 in the total sum, total count will be ones*(arr. length-ones) and multiply by two due to one repetition of all of this pair.

### Implementation

``````public Solution{
public static int HammingDistance(int[] arr) {
int total = 0; // Initialize result
// traverse over all bits
for (int i = 0; i < 32; i++) {
// count number of elements
// with i'th bit set
int ones = 0;

for (int j = 0; j < n; j++)
if ((arr[j] & (1 << i)) != 0)
ones++;
total += (ones * (n - ones) * 2);
}

}
public static void main(String args[]){
int arr[]={5,10,4};
//For printing the function
System.out.println(HammingDistance(arr));
}
}``````

OUTPUT

``8``

## Analysis of Complexity

### Time Complexity

Time complexity will be O(n), where we have to find different bits of pairs.

### Space Complexity

It will be O(1). No extra space was required.

1). What is the hamming distance?

Answer: Hamming Distance is comparing two binary data strings of equal length. It is the number of bit positions in which two bits are different.

2). How many approaches to solving this problem?

Answer: There can be many approaches to solve this problem of bit manipulation, but the most efficient approach will be one where time complexity is O(n) and space complexity is O(1).

## Key Takeaways

Here we have learned about one of the famous problems of bit manipulation, i.e., Pairwise Sum of Hamming Distance. We have tried two approaches over here. We have discussed two approaches. The first one was brute force, and the other one was an efficient approach along with Java code.

Check out this problem - XOR Queries On Tree

For better understanding, you can also practice more questions of a similar type, Hamming DistanceNumber of 1 Bit, and many more.

On Coding Ninjas Studio, try to solve the problem by yourself.

Live masterclass