Different Bits Sum Pairwise

Posted: 8 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.
Try Problem