** Welcome Back Reader!**

In this article we will discuss the next problem based on **'Bit Manipulation'** i.e. **'Sum of Bit Difference of All Pairs'**. This problem is an easy one plus interesting too.

Before you move any further, it is advised that you give this problem a fair try.

**Important Links :** Problem Link , Solution Video

Let's jump to the problem.

In this problem you are given an array of n numbers.**All you need to do is to find the sum of bit differences in all pairs that can be formed from n numbers.**

Bit difference of two numbers is defined as the count of different bits at the same positions in binary representations of two numbers.

**Sample Input:** 3

1 2 3**Sample Output:** 8

**How?**

We will see that further.**For more clarity of the question, watch part of the video.**

- 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 summarize, 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.
- But the brute approach would result in O(n^2) 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; therefore we say that the 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).

**For more clarity of this part, watch part of the video.**

**Let's try to code this!**

**For more clarity of this part, watch part of the video.**

java; true";

The time complexity for the function is linear as we are traversing on every element of the array.

The space complexity for the function is constant.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our

Trust me it will just get easier to understand after you have watched the solution video.

You can contact us via our website.

Doubts, suggestions and feedback are always welcomed.

It is also advised that you follow the sequence of modules and questions which is there on our website.

Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an optimistic future!

Happy Coding!