sum of xor of all pairs-GFG

This problem, which I took like a few days ago and was a fairly interesting one, cause it makes us think that to get the pairs its not necessary to get the pairs. Meaning sometimes the question just explains us the way that looks all good but it is not the way that we will have to proceed.

For e.x., in this problem I was busy thinking of how can I make the process of O(n^2) to O(n), I thought of all the ways of memoizing or some sort of xor inside idea that would help me, but the problem was that I was just trying to connect the dots in the way that the problem statement told me. 

I was trying to get a better way to get the pairs of the array. But the problem is that there is no way for that. The core of this problem was to identify the bit leveled idea that we could use. It is to get the contribution of individual bits in the overall summation. 

Just thinking the numbers in form of bits and then visualize those numbers written in a column.

Now, just think of say LSB(least significant bit) and try the same thing that we were doing before, making pairs of each bit with every other bit. With enough presence of mind you should be able to notice that every 1 is gonna give a 1 only with a 0. That's what happens in XOR right? 1 ^ 0 is 1 and 0 ^ 1 is 1 else all cases 0. 

        what 'bout 0^0? ;)

So... the number of 1's in this bit position will give how many 1's? that will be no. of ones*no. of zeroes

And that's it, we just need the freq of 1's and 0's in every bit position and then get the contribution(means the number of 1's in that position) and ofcourse then we are gonna multiply that with the value of that bit.

for ex. 1st position from left has a value of 1, then 2,4,8,16....

That's the only thing that this question needed.

Such types of problems are like testing your pattern recognition and yah course you were required to have knowledge of xor operator. The tricky part here is the way they explain the problem to you. and then you are just with O(n^2) in your mind, atleast I was.

Problem Statement:

Given an array of N integers, find the sum of xor of all pairs of numbers in the array arr. In other words, select all possible pairs of i and j from 0 to N-1 (i<j) and determine sum of all (arri xor arrj).

Example 1:

Input : arr[ ] = {7, 3, 5}
Output : 12
Explanation:
All possible pairs and there Xor
Value: ( 3 ^ 5 = 6 ) + (7 ^ 3 = 4)
 + ( 7 ^ 5 = 2 ) =  6 + 4 + 2 = 12

Example 2:

Input : arr[ ] = {5, 9, 7, 6} 
Output :  47
Explanation:
All possible pairs and there Xor
Value: (5 ^ 9 = 12) + (5 ^ 7 = 2)
 + (5 ^ 6 = 3) + (9 ^ 7 = 14)
 + (9 ^ 6 = 15) + (7 ^ 6 = 1)
 = 12 + 2 + 3 + 14 + 15 + 1 = 47

Your Task:
You do not have to take input or print output. You only need to complete the function sumXOR() that takes an array (arr), sizeOfArray (n), and return the sum of xor of all pairs of numbers in the array.

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).

Constraints
2 ≤ n ≤ 105
1 ≤ arr[i] ≤ 105

Code Implementation:

class Solution:

    def sumXOR (self, arr, n) :

       

        ans=0

        get_bit=1

        curr_bit_val=1

        for i in range(32):

            ones,zeros=0,0

            # getting the stats of this bit in all numbers

            for i in arr:

                if((i&get_bit)==0):

                    zeros+=1

                else:

                    ones+=1

                   

            # the total contribution of this bit

            total=ones*zeros

           

            # total bits contributed multiplied by the value of this bit

            ans+=total*curr_bit_val

           

            # updating the value of curr bit

            curr_bit_val*=2

           

            # also updation in the value of get_bit

            get_bit<<=1    

               

        return ans