```
/*
My solution:
- Do Xor of all elements with A[0]
- Keep track of how many numbers has bit = 1 at bit positions from 0 to 31 (i.e total bits in INT_MAX)
- Next, to find the same information with A[i]
- no need to loop through all the numbers again
- A[i] Xor A[0] will have the bit 1 at places where A[i] has different bit than A[0]
- where A[i] Xor A[0] has bit 0, there A[i] and A[0] has same bit so the count is same as before
- where A[i] Xor A[0] has bit 1, they have opposite bit at that pos, so all the previous 1s should be 0s, and all 0s should be 1s
- so the count (i.e count of 1 bits) at pos[j] should be n - count[j]; where n = total num of elements to compare
Time Complexity: O(n)
Space Complexity: O(n)
*/
int countBits(int a) {
int retval = 0;
while (a) {
if (a & 1)
retval++;
a >>= 1;
}
return retval;
}
bool bit_at_pos(int a, int pos) {
return (a & (1 << pos));
}
void fill_num_bits(int a, int n, int num_bits_at_pos[]) {
for (int i=0; i<n; i++) {
num_bits_at_pos[i] += bit_at_pos(a, i) ? 1: 0;
}
}
int Solution::cntBits(vector<int> &A) {
const int MOD = 1e9+7;
int n = countBits(INT_MAX);
long long retval = 0;
int num_bits_at_pos[n];
for (int i=0; i<n; i++)
num_bits_at_pos[i] = 0;
for (int j=0; j<A.size(); j++) {
fill_num_bits(A[0] ^ A[j], n, num_bits_at_pos);
}
for (int i=1; i<A.size(); i++) {
int a = A[0] ^ A[i];
for (int j=0; j<n; j++) {
if (bit_at_pos(a, j))
retval += A.size() - num_bits_at_pos[j];
else
retval += num_bits_at_pos[j];
retval %= MOD;
}
}
for (int i=0; i<n; i++) {
retval += num_bits_at_pos[i];
retval %= MOD;
}
return retval;
}
```

# My Solution, O(n) complexity

**bipin-oli**