# Different Bits Sum Pairwise

Posted: 8 Jan, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### 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.