Total Hamming Distance

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);
         	}
    	}
    	return total; 
  	}
  	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;
      	}
      	return total;
  	}

 	//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));

  	}

}

You can also try this code with Online Java Compiler

Run Code

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);
        }
 
        return total;
    }
    public static void main(String args[]){
        int arr[]={5,10,4};
         //For printing the function
        System.out.println(HammingDistance(arr));
    }
}

You can also try this code with Online Java Compiler

Run Code

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.

Frequently asked questions

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 Distance, Number of 1 Bit, and many more.

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