Pairwise Sum of Hamming Distance
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.
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.
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.
For each test case, return the sum of Hamming Distance for all the pairs.
You are not required to print anything just implement the given function.
1 <= T <= 10 1 <= N <= 10^4 0 <= ARR[i] <=10^9 Time limit: 1 second
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.
- Initialize Hamming Distance as 0.
- While A>0 or B>0
- If (A%2 != B%2) , then increment Hamming Distance by 1.
- Set A to A/2.
- 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.