 # My Solution, O(n) complexity

#1
``````/*
My solution:
- Do Xor of all elements with A
- 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 will have the bit 1 at places where A[i] has different bit than A
-   where A[i] Xor A has bit 0, there A[i] and A has same bit so the count is same as before
-   where A[i] Xor A 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 ^ A[j], n, num_bits_at_pos);
}

for (int i=1; i<A.size(); i++) {
int a = A ^ 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;
}``````