C++ O(n) complexity Solution


#1

_Think of O(n)
Use a loop of constant time (32 times) and another loop which iterates the elements of arrays.

In the for loop of 32 iterations, first iteration can give us the number of elements having 1 as 32nd bit and number of elements having 0 as 32nd bit. Product of these two numbers gives the sum of hamming distances of all pairs for 32nd bit. This happens 32 time to get the total sum_
Return sum*2 because we need to consider (a,b) as well as (b,a)

int Solution::hammingDistance(const vector<int> &A) {
int n = A.size();
long long int ans = 0;
int mod = pow(10,9)+7;

for(int i=31;i>=0;i--)
{
    long long int ones = 0, zeroes = 0;
    for(int j=0;j<n;j++)
    {
        int k = A[j]>>i;
        if(k&1) ones++;
        else zeroes++;
    }
    ans = (ans+(ones*zeroes))%mod;
}
return ans*2%mod;

}