Hello friends! Welcome to GeeksforGeeks. In

this video, we are given a problem that is to find the sum of bit differences among all

the pairs. The problem says that, given an array of integers

and we are required to find the sum of the bit differences in all the pairs that can

be formed from the given array. Now, Bit differences, the word seems confusing.

Here, bit difference of particular pair say x,y is the count of number of bits that are

different or we can say complementary in x and y. For example,

Take arbitrary input as x equal to 3 and y equal to 6, now the bits that are complementary

are highlighted here, Since we find complementary bits at two positions,

hence we say that bit difference of x and y is equals to 2. Now our task is to count

the sum of bit difference of every possible pair from the given array of integers.

As an example, now take the input array consisting of 1, 3 and 6. There are in all 9 possible

pairs shown here along with the count of their respective bit differences.For example bit

difference value of 1 and 3 is equals to 1 and bit difference of 1 and 6 is equals to

3. Now we take the sum of all the bit differences and return the sum as an answer which is equal

to 12 in this case. Let’s now carry on with the simple solution to this problem and then

look for the better alternative. One of the simple approaches, where we compute

the bit difference value for the each possible pair one by one and then update the global

sum variable with the sum of the calculated bit difference value for the each pair. Here

we would pair every element with all other elements in the array and for the array

containing n integers we would have n square possible pairs,

as you might have seen in our previous example for 3 elements 1,3 and 6,overall we had 9

possible pairs. Hence this would take the time complexity

of the order Of n square. Also, in this case our space remains constant throughout, hence

that would give us the space complexity of big O of 1. Now apart from this, we have an

efficient approach also which would solve the given problem in the time complexity of

the order of n. Let’s go for that. The efficient approach is based on the fact

that ultimately the problem is asking to count all the zero-one pairs at all possible bit

positions. This approach assumes that each integer in the given array is of fixed number

bits for example say 32 bits. Now what we do is we instead of going for every possible

pair, we traverse each bit position, and for any arbitrary bit position i, we count the

number of integers having the ith bit as set. Now if the variable count stores the number

of integers having ith bit as set, then number of integers having ith bit as unset, would

be n minus count and their product multiplied by 2 would give us all combinations of the

all possible complementary bit pairs at the ith position. We compute this product for

every bit in the 32 bit integer and add it to the global sum variable. At last we return

this sum variable as the answer. To make this more clear, let’s take the same example

again. Here the binary representation of 1, 3 and

6 are shown, and fixed bit length is assumed to be 3. Initially sum variable is set to

zero. Now we first check the least significant bit and look for the integers having LSB as

set. Here we find two such integers 1 and 3. So

the calculated product is equal 2 ( that is the number of integers having the lsb as set)

into 1( that is the number of integers having lsb as unset) into 2 which is equal to 4 and

adding that to the sum variable, it becomes equal to 4.

Now we go on for the second bit and we again find 2 integers 3 and 6 having this bit position

as set. So again the product is equal to 4 and adding this to the sum variable would

give us the sum variable equal to 8. At last we would do the same for the most

significant bit and we find only 1 integer that is 6 having this bit position as set,

so the product again becomes equal to 4 and this time the sum variable becomes equal to

12. Hence, what we get is the sum variable equal

to 12 as an answer which is same as that being shown earlier. Now Let’s see the implementation

for the given approach. Here we have a function named sum bit differences

which takes the array of integers along with its size n as the arguments. Now we first

take the answer variable and initialize that with 0. Next we run a for loop which iterates

for each bit position of the 32 bit integers. Now inside for loop we take an another integer

named count which stores the number of integers having ith bit as set. We calculate those

integers by running an another for loop with the value of j from zero to n, each time we

check for the set bit at the ith position by taking the bitwise AND operation of the

integer with the 1 left shift i, and if we find the bit as set then we increment the

counter count. Further in the external for loop we calculate the product of count into

n minus count multiplied by 2 to get all possible 0-1 pairs at the ith bit position and finally

add it to the answer variable. This answer variable at last would give us the sum of

all the bit differences among all the pairs. The complexity analysis of this approach is

as follows: Since, the length of external for loop is kept fixed, hence we would consider

only the inner for loop for the complexity, and since it iterates over all the integers

in the given array and array has n integers, the algorithm takes Order of n in time. And,

since our space requirements remains constant throughout, the space complexity remains Big

O(1). I hope you have understood the two ways in

which we can find the sum of bit differences among all pairs. Thanks for watching. Please

leave us your comments.

Whats the Logic behind the Efficient Solution?

https://leetcode.com/problems/total-hamming-distance/discuss/96226/Java-O(n)-time-O(1)-Space . In geeks for geeks, they unnecessarily assume 1,3 and 3,1 as different pairs. But in Leetcode, they don't.

Not helpful. Need more explanation how you got that formula

smjhh mein aaya kyaaaaaaaaaaaaaaaaa!!!!!!!!!!!!!!!

I have a better and easier way to do this

Hi

If the input for one test case with two array values of 1 and -6 gives the expected output as 60.

Could anyone please explain this?