# HackerEarth Xor sum problem solution

In this HackerEarth Xor sum problem solution, You are given an array A[] of size N. Now you are given Q queries to be performed over this array. In each query, you are given space-separated integers L and R. For each query, you need to find the summation of the xor-sum of all triplets (i,j,k) of the sub-array L...R, where L <= I < j < k <= R.

In short, you need to find sigma(A[i] xor A[j] xor A[k]), over all triplets (i,j,k), such that L <= i < j < k <= R. Print the answer for each query , Modulo 10^9 + 7.

## HackerEarth Xor sum problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long long int#define MOD 1000000007ll n,q,a[100005],seg[400005][45],l,r,po[100005];/*void build(ll node,ll st,ll en){    if(st==en)    {        for(ll i=0;i<=42;i++)        {            if(a[st]&(1<<i))            seg[node][i]=1;        }    }    else    {        ll mid=(st+en)/2;        build(2*node,st,mid);        build(2*node+1,mid+1,en);        for(ll i=0;i<=42;i++)        {            seg[node][i]=seg[2*node]+seg[2*node+1];        }    }}ll qry(ll node,ll st,ll en,ll l,ll r,ll idx){    if(st>en||st>r||en<l||l>r)    return 0;    else if(st>=l&&en<=r)    return seg[node][idx];    else    {        ll mid=(st+en)/2;        return qry(2*node,st,mid,l,r,idx)+qry(2*node+1,mid+1,en,l,r,idx);    }}*/void create(){    ll i,j;    for(i=0;i<=42;i++)    {        for(j=1;j<=n;j++)        {            seg[j][i]=seg[j-1][i];            if(a[j]&(1LL<<i))            seg[j][i]++;        }    }}int main(){    //ios::sync_with_stdio(0);    //cin.tie(0);    freopen("in05.txt","r",stdin);    freopen("out05.txt","w",stdout);    ll i,j,k;    cin>>n;    po[0]=1;    for(i=1;i<=100002;i++)    {        po[i]=2*po[i-1];        po[i]%=MOD;    }    for(i=1;i<=n;i++)    {        cin>>a[i];    }    //build(1,1,n);    create();    cin>>q>>j;    while(q--)    {        cin>>l>>r;        ll cnt1,cnt0,ans=0,ans1=0;        for(i=0;i<=42;i++)        {            cnt1=seg[r][i]-seg[l-1][i];            cnt0=r-l+1-cnt1;            ans=cnt1*(cnt0*(cnt0-1))/2;            ans+=(cnt1*(cnt1-1)*(cnt1-2))/6;            ans%=MOD;            ans=ans*po[i];            ans%=MOD;            ans1+=ans;            ans1%=MOD;        }        cout<<ans1<<"\n";    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>using namespace std;typedef complex<double> base;typedef long double ld;typedef long long ll;#define pb push_backconst int maxn=(int)(2e5+5),LN=41;const ll mod=(ll)(1e9+7);ld pi=2.0*acos(0.0);ll a[maxn];int pre[LN][maxn];int mul(ll a,ll b){    a%=mod;b%=mod;        ll ret=(a*b);        if(ret>=mod)    {        ret%=mod;    }        return (int)ret;}int add(ll a,ll b){    a%=mod;b%=mod;        ll ret=a+b;        if(ret>=mod)    {        ret%=mod;    }        return (int)ret;}int sub(ll a,ll b){    a%=mod;b%=mod;        ll ret=a-b;        if(ret<0)    {        ret+=mod;    }        return (int)ret;}static int poww(ll a,ll b){    ll x=1,y=a;            while(b>0)    {           if(b%2)        {            x=mul(x,y);        }                    y=mul(y,y);b/=2;    }            return (int)(x%mod);}const int inv_6=poww(6,mod-2),inv_2=poww(2,mod-2);int nC3(ll n){    if(n<3)    {        return 0;    }        return mul(mul(n,mul(n-1,n-2)),inv_6);}int nC2(ll n){    if(n<2)    {        return 0;    }        return mul(n,mul(n-1,inv_2));}int main(){       int n;scanf("%d",&n);        assert(n>=1 && n<=(int)(1e5));        for(int i=1;i<=n;i++)    {        scanf("%lld",&a[i]);                assert(a[i]>=1 && a[i]<=(ll)(1e12));    }        for(int j=0;j<LN;j++)    {        int now=0;ll zz=(1ll<<j);                for(int i=1;i<=n;i++)        {            if((zz&a[i])!=0)            {                   now++;            }                        pre[j][i]=now;        }    }        int q,two;scanf("%d%d",&q,&two);        assert (q>=1 && q<=(int)(5e5) && two==2);        for(int i=0;i<q;i++)    {        int l,r;scanf("%d%d",&l,&r);                assert (l>=1 && l<=r && r<=n);                int res=0,size=(r-l+1);                for(int j=0;j<LN;j++)        {            int val1=(pre[j][r]-pre[j][l-1]),val0=size-val1;                        int zz1=mul(val1,nC2(val0)),zz2=nC3(val1);                        res=add(res,mul(1ll<<j,add(zz1,zz2)));        }                printf("%d\n",res);    }        return 0;}`