Last Updated: 8 Jan, 2021
Different Bits Sum Pairwise
Easy
Asked in companies
You are given an arbitrary array ‘arr’ consisting of 'N' non-negative integers. You need to find the sum of bit differences of all the pairs that can be formed in the given array.
In simple words, let us define f(x, y) as the count of different bits at the same position in the binary representations of two integers, x and y.
You need to find the summation of f over all possible values of x and y in the input array I.e sum( f(arr[i], arr[j])) for all 0 <= i < N and 0 <= j < N.
For Example :
f(2, 3) = 1, as 2 → 0010 and 3 → 0011, only the last bit is different in both the numbers, hence f(2, 3) is 1.
Note :
As the final answer may be very large, return your answer modulo 10^9 + 7.
Input Format :
The first line of the input contains a single integer T, representing the number of test cases.
The first line of each test case consists of a single integer 'N', representing the number of elements in the given array.
The second line of each test case contains 'N' space-separated integers, denoting the elements of the array.
Output Format :
For each test case, print the sum of bit differences among all possible pairs in the given array.
Print the output of each test case in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= N <= 10^4
0 <= arr[i] < 10^9
Time Limit: 1sec
Approaches
An easy way to solve this problem will be to run a double loop to consider every possible pair in the given array and add its count of different bits to the final result variable.
Algorithm
- Create an integer valuable ‘ans’ to store the final answer and initialize it with 0.
- Run a nested loop for i and j, with i going from - i to n-1 and j going from i to n.
- For every pair i and j, we have to count the number of bit differences between arr[i] and arr[j]. To do this, we first find the bitwise AND(stored in bitwiseAnd) of arr[i] and arr[j] and bitwise OR(stored in bitwiseOr) or arr[i] and arr[j].
- Then, count the number of set bits in bitwiseOr and bitwiseAnd. Let these be nBits1 and nBits2 respectively.
- The absolute difference between nBits1 and nBits2 will be the number of bit differences between arr[i] and arr[j]. Let this be equal to ‘count’
- Add (2*count) to the final ans variable as each pair has to be considered twice in the final answer.
- Return ans and terminate.
- We know that all integers can be represented using 32 bits(or some other fixed number of bits).
- Now to find the total number of different bits in the entire array, we first count the number of set bits at each position (0 to 31). Let this be equal to count.
- If there are ‘count’ set bits at ith bit position, there must be exactly (n-count) unset bits at ith position.
- Hence, the count of differences in bits at ith position would be equal to (count)*(n-count).
- The reason for this formula is that as every pair having one element which has set the bit at i’th position and a second element having an unset bit at i’th position contributes exactly 1 to sum, therefore total permutation count will be count*(n-count).
- We multiply this product by 2 because every pair appears exactly twice the array and contributes to the final sum twice.
- Add (2*count*(n-count)) to the final ans variable.
- Return ans and terminate.
Similar problems