Pairwise AND Sum | CodeChef Solution

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

Task

You are given a sequence of N integer numbers A. Calculate the sum of A_i AND A_j for all the pairs (i, j) 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, A_i <= 1.
Subtask 2 (39 points): N <= 1000, A_i <= 10⁹.
Subtask 3 (21 points): N <= 10⁵, A_i <= 1.
Subtask 4 (27 points): N <= 10⁵, A_i <= 10⁶.

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

# 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
	{
		// your code goes here
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] as = br.readLine().split(" ");
		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.