Sum Of Bit Differences Of All Pairs
1. You are given an array of n numbers.Input Format
2. You have to find the sum of bit differences in all pairs that can be formed from n numbers.
3. Bit difference of two numbers is defined as the count of different bits at same positions in binary representations of two numbers.
A number nOutput Format
a1
a2..
n numbers
Check the sample ouput and question video.Question Video
1 <= n <= 10^9Sample Input
1 <= arr[i] <= 10^9
3Sample Output
1 2 3
8
-
Editorial
In this problem, we are given an array of integers and we need to determine the sum of bit differences in all pairs that can be formed from n numbers.
For example
N = 3
Array [N] = {1, 2, 3}
1 -> 0 0 1
2 -> 0 1 0
3 -> 0 1 1
For pair (1, 2) difference at position 0 and 1 => count = 2
For pair (1, 3) difference at position 1 => count = 3
For pair (2, 3) difference at position 0 => count = 4
For pair (2, 1) difference at position 0 and 1 => count = 6
For pair (3, 1) difference at position 1 => count = 7
For pair (3, 2) difference at position 0 => count = 8
Hence our result is 8.
To summarise, we need to consider every possible pair (Ai, Aj) where i != j and for every such pair we need to count the bit differences. The brute force approach would be to generate every pair by two nested loops and for every pair count the set bits for the XOR of the pairs using Kerninghams algorithm. This would result in O(n2) time complexity.
A way to optimize this code is instead of generating all pairs we can traverse on every bit from 0 to 31 and for every bit, we can count the numbers having bit as a set and as unset. Later on, we can calculate the count by the expression: count0 * count1 * 2.
Let us take the above example again to check the validity of the expression:
N = 3
Array [N] = {1, 2, 3}
1 -> 0 0 1
2 -> 0 1 0
3 -> 0 1 1
For index 0: count0 = 1 and count1 = 2 => ans += 1*2*2 = 4
For index 1: count0 = 1 and count1 = 2 => ans += 1*2*2 = 8
For index 2: count0 = 3 and count1 = 0 => ans += 3*0*2 = 8
Hence we get 8 as our result.
Hence, our expression is valid.
The insight behind the expression is that by multiplying count0 and count1 we generate the pairs which have different bit values at this position and a multiplication by 2 is needed to check for the type (2, 1) for (1, 2).
Time Complexity: O(32*n)
The time complexity for the function is linear as we are traversing on every element of the array.
Space Complexity: O(1)
The space complexity for the function is constant.
-
Asked in Companies
-
Related Topics