Last Updated: 8 Jan, 2021

Pairwise Sum of Hamming Distance

Moderate

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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:

Initialize Hamming Distance as 0.
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.

Solve now

02 Approach

The idea is to calculate the answer for each bit separately. We will be building two arrays COUNT_ZERO and COUNT_ONE which will store the total occurrences of 0 and 1 respectively at each of the positions in the binary representation of the numbers. For any bit say i, the contribution of it to the final answer is 2*COUNT_ZERO[i]*COUNT_ONE[i] because to get a Hamming Distance of 1 we need a pair of 0 and 1 and there are 2*COUNT_ZERO[i]*COUNT_ONE[i] such pairs at the ith position. Therefore the final answer will be the sum of 2*COUNT_ZERO[i]*COUNT_ONE[i] over all values of i.

Steps:

Initialize two arrays COUNT_ZERO and COUNT_ONE of size 32 with all values 0.
Do a for loop for i=0 to N-1
1. Initialize j=0.
2. While j<32
  1. If (A[i]%2==0), then increment COUNT_ZERO[j] by 1 otherwise increment COUNT_ONE[j] by 1.
  2. Divide A[i] by 2.
  3. Increase j by 1.
Initialize answer = 0.
Do a for loop for i=0 to 31
1. Add 2*COUNT_ZERO[i]*COUNT_ONE[i] to the answer.
Return the final answer.

Solve now