My solution is o(n) but still gives partially correct answer


#1

int Solution::cntBits(vector &A) {
long long int res=0;
for(int i=0;i<32;i++)
{
long long int num1s=0,num0s=0;
for(int j=0;j<A.size();j++)
{
if(A[j]%2!=0)
num1s++;
else
num0s++;
A[j]=A[j]>>1;
}
res+=((num1s%1000000009)*(num0s%1000000009))%1000000009;
}
return ((res%1000000009)*2)%1000000009;
}


#2

Mod is 1000000007 instead of 1000000009


#3

convert all int into long long int as it might not be taking larger values or size of n can be very large