Sum Of Bit Differences Of All Pairs

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given an array of n numbers.
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.
Input Format 
A number n
a1
a2..
n numbers
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= n <= 10^9
1 <= arr[i] <= 10^9
Sample Input 
3
1 2 3
Sample Output 
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






Video Solution

Code Solution

Run
 
Run
Id Name