Problem resolved in O(N) and no Failed for Long-Range cases

interview-questions
Tags: #<Tag:0x00007f242d8fb760>

#1

Comment body goes here.int Solution::hammingDistance(const vector &A) {

int bit_idx = 0;
int num_idx = 0;
unsigned long long int total_sum = 0, ones = 0, zero = 0;

for (bit_idx = 0; bit_idx < 32; bit_idx++)
{
    ones = 0;
    zero = 0;

    for (num_idx = 0; num_idx < A.size(); num_idx++)
    {
        if (A[num_idx] < 0)
            continue;
        if (1 == A.size())
            break;    
        if ((A[num_idx] >> bit_idx) & 1)
        {
            ones++;
        }
        else
        {
            zero++;
        }
    }
    total_sum += (ones * zero);
}

return ((total_sum * 2)%(1000000007));
}


#2

Hey, I had the same problem!
After thinking long enough, I checked the solution.

There were two changes:

  1. Instead of using “%1000000007” they were using “%mod” (they declared: int mod =1000000007).
  2. total_sum += (ones * zero)%mod;
    if(total_sum>mod) total_sum-= mod;

I understood the second but the first has blown my mind.
My test cases are not passing if I directly use “1000000007” instead taking “mod”. I don’t know why!