My Solution, O(n) complexity


#1
/*
    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;
}