Find sum of different corresponding bits for all pairs

A subtle problem to solve in O(n), here are some hints:

1.) The range of values in the input indicates that it is an array of signed 32 bit integers
2.) Negative numbers are represented in two's compliment
3.) Use the fact that all numbers are 32 bits to come up with a linear solution

AND given in question that:
You are given an array of N integers, A1, A2 ,…, AN. Find sum of f(Ai, Aj) for all pairs (i, j) such that 1 ≤ i, j ≤ N.

Return the answer modulo 109+7.

Assume that all values in input have only 1 bit i.e. Ai = 0 or 1.
Lets say A = count of elements which are 0
and B = count of elements which are 1

In this case our answer is just 2AB, since each such pair contributes 1 to answer.

 we can combine this logic if we have multiple bits.

Note that all bits are independent in counting, since we are counting number of bits which are different in each pair.
So, we just do the same process for all different bits. Since Ai is an integer, we just have to do this for 31 different bits, so our solution is O(31*N).

Constraints:

1 ≤ T ≤ 70
1 ≤ N ≤ 104
-2,147,483,648 ≤ A[i] ≤ 2,147,483,647

SIMPLE AND UNDERSTABLE SOLUTION:-

#include <bits/stdc++.h>
using namespace std;
int main()
{
long long t,n,i,j,a[100005],ans,m=1000000007;
cin>>t;
while(t--)
{
cin>>n;

long long dp[100]={0};

for(i=1;i<=n;i++)
{
cin>>a[i];
}

for(i=1;i<=n;i++)
{
      for(j=0;j<32;j++)
{
            if((1<<j)&a[i])
               dp[j]++;
} 
}
ans=0;
for(i=0;i<32;i++)
{
ans=(ans%m+((dp[i]%m)*((n-dp[i])%m))%m)%m;
}

cout<<(ans*2)%m<<endl;
}
return 0; }