Bit Difference

We define f (X, Y) as number of different corresponding bits in binary representation of X and Y. For example, f (2, 7) = 2, since binary representation of 2 and 7 are 010 and 111, respectively. The first and the third bit differ, so f (2, 7) = 2.

You are given an array A of N integers, A1, A2 ,…, AN. Find sum of f(Ai, Aj) for all ordered pairs (i, j) such that 1 ≤ i, j ≤ N. Return the answer modulo 109+7.

• Time : O(n)
• Space : O(1)

class Solution{
public:
    int countBits(int N, long long int A[])
    {
        long long int res = 0, mod = 1e9 + 7;
        for(long long int i = 0; i < 32; i++) {
            long long int count = 0;
            for(long long int j = 0; j < N; j++) {
                if(A[j] & (1<<i)) count++;
            }
            
            res = (res + count * (N - count) * 2 % mod) % mod;
        }
        return res;
    }
};