Efficient Solution


#1

int dp[32][2];memset(dp,0,sizeof(dp));
int n=a.size(),i,j,ans=0,m=1e9+7;
for(i=0;i<n;i++)
{
int x=0;
if(i){
for(j=31;j>=0;j–)
{
int f=0;
int y=(a[i]&(1<<j));
if(y) f=1;
x+=(dp[j][1-f]);
//cout<<x<<" ";
}
ans+=(2*x);ans%=m;}
for(j=31;j>=0;j–)
{
if(a[i]&(1<<j)) dp[j][1]++;
else dp[j][0]++;
}
}
return ans;