Different Bits Sum Pairwise

Easy
0/40
Average time to solve is 15m
profile
Contributed by
131 upvotes
Asked in companies
BarclaysGoogle inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2
1 2
2
6 6
Sample Output 1 :
4
0
Explanation for Sample Input 1 :
Test Case 1:
All the possible pairs in the given array are:-
f(1, 1) - as both numbers are same, no. of bit differences is 0
f(1, 2) - 1 in binary is (0001) and 2 in binary is (0010). There are 2 bits which are different in both the numbers. Hence, no. of bit differences is 2.
f(2, 2) - as both numbers are the same, no, of bit differences is 0
f(2, 1) - same as (1, 2), hence no. of bit differences is 2.
Summing the above values (0+2+0+2) we get 4. Hence, the output is 4.

Test Case 2:
There is only one possible pair (6,6). As both the numbers are sum, the output is 0.
Sample Input 2 :
2
3 
1 3 5
4
4 6 7 8
Sample Output 2 :
8
26
Hint

Run two loops to count the number of bit differences between all possible pairs

Approaches (2)
Brute Force Approach

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.
Time Complexity

O(N^2), where ‘N’ is the number of elements in the array.

 

As we are running two nested loops, time complexity is O(N^2)

Space Complexity

O(1)

 

We are using constant extra space.

Code Solution
(100% EXP penalty)
Different Bits Sum Pairwise
Full screen
Console