# Pairwise AND Sum | CodeChef Solution

Hello coders, today we are going to solve Pairwise AND Sum CodeChef Solution whose Problem Code is AND.

You are given a sequence of N integer numbers A. Calculate the sum of Ai AND Aj for all the pairs (ij) where i < j.

## Input Format

The first line of input consists of the integer N.
The second line contains N integer numbers – the sequence A.

## Output Format

Output the answer to the problem on the first line of the output.

Example

Sample Input

``````5
1 2 3 4 5``````

Sample Output

``9``

Scoring

Subtask 1 (13 points): N <= 1000, Ai <= 1.
Subtask 2 (39 points): N <= 1000, Ai <= 109.
Subtask 3 (21 points): N <= 105Ai <= 1.
Subtask 4 (27 points): N <= 105Ai <= 106.

## Solution – Pairwise AND Sum

### C++

```#include <bits/stdc++.h>
using namespace std;
#define mod (long long int)1000000007
#define ll long long int
ll power(ll a,ll b){
if(b == 0){return 1;}
ll ans = power(a,b/2);
ans = ((ans % mod) * (ans % mod)) % mod;
if(b & 1){ans = ((ans % mod) * (a % mod)) % mod;}
return ans;
}
int main() {
int n;
cin>>n;
vector<ll>arr(33,0);
long long a;
int i;
for(int k=0;k<n;k++){
cin>>a;
i = 0;

while(a){
if((a&1) == 1){arr[i] += 1;}
a>>=1;
i++;
}
}
ll ans = 0;
for(int k=0;k<=32;k++)
{
ans+=(arr[k]*(arr[k]-1)/2)*power(2,k);
}
cout<<ans<<endl;

return 0;
}```

### Python

```# cook your dish here

n = int(input())
lst = list(map(int, input().split()))
bit = [0]*30
ans = 0
for i in range(30):
cnt = 0
for x in lst:
if (x&(1 << i)):
cnt+=1
ans += ((cnt*(cnt-1))//2)*(1 << i)
print(ans)

```

### Java

```/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
long[] a = new long[n];
for (int i=0; i<n; i++) {
a[i] = Long.parseLong(as[i]);
}

long sum =0;
for(int j=1; j < n; j++) {
for (int i=0; i<j; i++) {
sum += a[i] & a[j];
}
}
System.out.println(sum);
}
}
```

Disclaimer: The above Problem (Pairwise AND Sum) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.