Pairwise AND sum


You are given a sequence of N integer numbers A. Calculate the sum of Ai AND Aj for all the pairs (i, j) where i < j. The AND operation is the Bitwise AND operation, defined as in here. Input: The first line of input consists of the integer N. The second line contains N integer numbers - the sequence A. Output: The answer to the problem on the first line of the output Test Case 1 Input (stdin) 5 1 2 3 4 5 Expected Output 9 Test Case 2 Input (stdin) 4 1 2 3 4 Expected Output 3

Program :

#include <iostream>

#include <bits/stdc++.h>

#include <sstream>

#include <cmath>

#include <algorithm>

#include <map>

#include <iterator>

#include <iomanip>

#include <queue>

#include <utility>

using namespace std;

#define ll long long int

#define c(x) ll x;cin>>x

#define cc(x,y) ll x,y;cin>>x>>y

#define ccc(x,y,z) ll x,y,z; cin>>x>>y>>z

#define db long double

#define fast cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)

#define inf 200000000000000

#define mod 1000000007

#define eps 1e-7

#define PI 3.1415926535897932385

#define pb push_back

#define bitc __builtin_popcountll

#define mp make_pair

#define ff first

#define ss second

#define all(ar) ar.begin(), ar.end()

#define len(x) (ll)(x).size()

#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)

#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)

#define repr(i,n) for (ll i = n - 1; i >= 0; i--)

#define frr(i,a,b) for (ll i = (a), _b = (b); i >= _b; i--)

#define foreach(it,ar) for (auto it = ar.begin(); it != ar.end(); it++)

#define fill(ar,val) memset(ar, val, sizeof(ar))

#define print(arr,n) rep(i,n) cout<<arr[i]<<" "; cout<<endl

#define print2(arr,n,m) rep(i,n){ rep(j,m) cout<<arr[i][j]<<" "; cout<<endl; }

#define dyn1(arr,n) ll* arr=new ll[n]; rep(i,n) arr[i]=0;

#define dyn2(arr,n,m) ll** arr=new ll*[(n)]; rep(i,n) arr[i]=new ll[m]; rep(i,n) rep(j,m) arr[i][j]=0

#define carr(arr,n) rep(i,n) cin>>arr[i]

#define carr2(arr,n,m) rep(i,n) rep(j,m) cin>>arr[i][j]

#define debug(a) cout<<" :: "<<#a<<" == "<<a<<endl

inline ll maxim(ll a,ll b) {if(a>b) return a; else return b;}

inline ll minim(ll a,ll b) {if(a<b) return a; else return b;}

inline bool equals(double a, double b){ return fabs(a - b) < 1e-9; }

ll gcd(ll a, ll b){ return b==0 ? a : gcd(b, a%b); }

ll modpow(ll b, ll e) {

ll ans=1; for(;e;b=b*b%mod,e/=2) if(e&1) ans=ans*b%mod; return ans;}


ll ncr(ll n,ll r)


  if(r>n) return 0;



    return 1;


  if(r==1) return n;





  string key=to_string(n)+"|"+to_string(r);



    ll answer=ncr(n-1,r-1)+ncr(n-1,r);



  //cout<<key<<" "<<m[key]<<endl;

  return m[key];


int modInverse(int a, int m)


    int m0 = m;

    int y = 0, x = 1;

    if (m == 1)

      return 0;

    while (a > 1)


        // q is quotient

        int q = a / m;

        int t = m;

        // m is remainder now, process same as

        // Euclid's algo

        m = a % m, a = t;

        t = y;

        // Update y and x

        y = x - q * y;

        x = t;


    // Make x positive

    if (x < 0)

       x += m0;

    return x;


ll arr[100003];

ll counti(ll i,ll n)


  ll count=0;








  return count;


int main()



  //freopen("input.txt", "r", stdin);

  //freopen("output.txt", "w", stdout);


  ll t=1;





    ll total=0;







  return 0;