Pairwise Sum of Hamming Distance

Posted: 8 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an array ARR having N integers. Your task is to find the sum of Hamming Distance for each pair of the array elements.

Hamming Distance for two given integers 'A' and 'B' is defined as the minimum number of bits that needs to be toggled to make both the integers equal.

For example:

Consider A=4 and B=7
Binary representation of 4 = 100
Binary representation of 7 = 111
For the given example, if we flip the values of the last two least significant bits of A to 1 then A will become 7. As we can change the value of A to B by 2 flips. Therefore the Hamming Distance, in this case, is 2.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array.

The second line of each test contains 'N' space-separated integers denoting the array elements.
Output Format:
For each test case, return the sum of Hamming Distance for all the pairs.
Note:
You are not required to print anything just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
0 <= ARR[i] <=10^9

Time limit: 1 second
Approach 1

The idea is to iterate through all the pairs of array elements, calculate their respective Hamming Distances and sum out all the values to find the overall answer. 

We will build an auxiliary function to calculate Hamming Distance of two integers A and B. The idea to calculate Hamming Distance is to iterate through the binary representation of both the integers moving from least significant to most significant bit. We increment the Hamming Distance by 1 for every position having different bit values.

 

Steps:

  1. Initialize Hamming Distance as 0.
  2. While A>0 or B>0
    1. If (A%2 != B%2) , then increment Hamming Distance by 1.
    2. Set A to A/2.
    3. Set B to B/2.

 

Now we can initialize the ANSWER as 0, Iterate through all the pairs of array elements, find the Hamming Distance using the above function and add it to the ANSWER.

In the end we will return the value of the sum of hamming distance.

Try Problem