The best solution concept explaination


#1
  1. We have all the numbers in a 32-bit format stored internally
  2. Iterate through columns (of bits) of all numbers (using bitwise shifts)
  3. Count number of 1’s and 0’s each (using bitwise AND)
  4. Make pairs, we can have 4 scenarios -> (0,0) , (1,1), (0,1) , (1,0)

We specifically need the last 2 scenarios, which would be -
No. of zeros * No. of ones + No. of ones * No. of zeros
i.e 2XY (X is no. of zeros, Y is no. of ones)

and voila we have our solution.

The solution uses bitwise shift operator and we do not really need to convert numbers to binary as that’s how they are actually stored in the computer.


#2

C++ [O(m*n), O(1)]; m being max no. of bits possible in a number in the array.

#define lim 1000000007
#define lli long long int
int Solution::hammingDistance(const vector<int> &A) 
{
    lli mx = *max_element(A.begin(), A.end()), res=0, n = A.size();
    for(int k=0; k<log(mx*2)/log(2); k++)
    {
        lli b=0;
        for(int i=0; i<n; i++)
            b = b + (A[i]&(1<<k)? 1 : 0);
        
        res = (res + (2*b*(n-b))%lim )%lim;
    }
    return res;
}