# HackerEarth Ma5termind and XOR Minimization problem solution

In this HackerEarth Ma5termind and XOR Minimization problem solution Mastermind is a bright student of his class. To judge his intelligence and speed his teacher has given him a question and he needs your help for solving it. The question is :

Given a sequence of N elements, find all subsequences of this sequence, then compute the sum of all these subsequences individually, finally, find the number of subsequences that give minimum XOR with a given value A. He can solve this question very quickly but now he needs your help as the number of such questions is very large.

## HackerEarth Ma5termind and XOR Minimization problem solution.

`#include<iostream>#include<string>#include<cstdio>#include<cstring>#include<climits>#include<bits/stdc++.h>using namespace std;#define mp make_pair#define pb push_back#define ll long long#define VI vector<int>#define PII pair<int,int>#define VII vector<PII >#define ft first#define sd second#define rz(v,n) v.resize(n)#define VL vector<ll>#define VLL vector<pair<ll,ll> >#define PLL pair< ll,ll >#define all(v) v.begin(),v.end()#define IT iterator// Input/Output#define print(v) printf("%d\n",v)#define printll(v) printf("%lld\n",v)#define scan(v) scanf("%d",&v)#define scanll scanf("%lld",&v)// loops#define FOR(i,a,b) for(int i=a;i<b;i++)#define RFOR(i,a,b) for(int i=a;i>=b;i--)#define rep(i,n) for(int i=0;i<n;i++)//extra#define ms(v,val) memset(v,val,sizeof(v))#define fill(v,val) fill(all(v),val)#define f_in(st) freopen(st,"r",stdin)#define f_out(st) freopen(st,"w",stdout)#define PIE 3.14159265358979323846264338327950#define MOD 1000000007#define ull unsigned long long#ifdef ONLINE_JUDGE inline void inp( int &n ) {    n=0;    int ch=getchar_unlocked();int sign=1;    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}    while(  ch >= '0' && ch <= '9' )            n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();    n=n*sign;  }#elseinline void inp(int &n){ cin>>n;}#endif#define MAX 100001#define TRIESIZE 2100001ll DP[MAX];bool S[MAX];bool trie[TRIESIZE];int P[21];void process(){  int i;  P[0]=1;  FOR(i,1,21)      P[i]=P[i-1]*2;}void update(int x){  int i;  int idx=0;  int p=1;  RFOR(i,19,0){    if(x&P[i]){      trie[2*idx+2]=1;      idx=2*idx+2;    }else{      trie[2*idx+1]=1;      idx=2*idx+1;    }  }}int query(int x){  int i;  int sum=0;  int idx=0;  RFOR(i,19,0){    if(x&P[i]){      if(trie[2*idx+2])        sum+=P[i],idx=idx*2+2;      else        idx=2*idx+1;    }else{      if(!trie[2*idx+1])          sum+=P[i],idx=idx*2+2;      else        idx=idx*2+1;    }  }  return sum;}int main(){  #ifndef ONLINE_JUDGE    f_in("in10.txt");    f_out("out10.txt");  #endif  int t;  t=1;  while(t--){   int n;   inp(n);   VI A(n);   int i,j;   S[0]=1;   DP[0]=1;   FOR(i,0,n) inp(A[i]);   int maxx=1;   FOR(i,0,n){     for(j=maxx;j>=0;j--){       if(S[j])       {         maxx=max(maxx,j+A[i]);         S[j+A[i]]=true;         DP[j+A[i]]+=DP[j];         DP[j+A[i]]%=MOD;       }     }   }   process();   int Q,x;   inp(Q);   FOR(i,1,MAX) if(S[i]) update(i);   while(Q--){     inp(x);     int ans=query(x);     printf("%d %lld\n",ans,DP[ans]);   }  }  return 0;}`

### Second solution

`#include <bits/stdc++.h>#define _ ios_base::sync_with_stdio(false);cin.tie(0);using namespace std;#define pb push_back#define pob pop_back#define pf push_front#define pof pop_front#define mp make_pair#define all(a) a.begin(),a.end()#define bitcnt(x) __builtin_popcountll(x)#define MOD 1000000007#define NIL 0#define MAXN 220001#define EPS 1e-5#define INF (1<<28)typedef unsigned long long int uint64;typedef long long int int64;int sum[100005];int a[105];struct node{    struct node *lchild,*rchild;    node(){        lchild=NULL;        rchild=NULL;    }};void ins(struct node *root,int val){    for(int j=30;j>=0;j--){        int x=val&(1<<j);        if(x){            if(root->rchild==NULL)            root->rchild=new node();            root=root->rchild;        }        else{            if(root->lchild==NULL)            root->lchild=new node();            root=root->lchild;        }    }}int quey(struct node *root,int val){    int ans=0;    for(int j=30;j>=0;j--){        int x=val&(1<<j);        if(x==0){            if(root->lchild){                root=root->lchild;            }            else{                ans|=(1<<j);                root=root->rchild;            }        }        else{            if(root->rchild){            ans|=(1<<j);            root=root->rchild;}            else            root=root->lchild;        }    }    return ans;}int main(){    int n,i,j;    scanf("%d",&n);    for(i=0;i<n;i++)    scanf("%d",&a[i]);    sum[0]=1;    for(i=0;i<n;i++){        for(j=100000;j>=a[i];j--){            if(sum[j-a[i]]){            sum[j]+=sum[j-a[i]];            if(sum[j]>=MOD){                sum[j]%=MOD;            }}}}        node *root=new node();    for(i=1;i<=100000;i++){        if(sum[i])        ins(root,i);    }    int q,u,fin;    scanf("%d",&q);    while(q--){        scanf("%d",&u);        int ans=quey(root,u);        printf("%d %d\n",ans,sum[ans]);    }    return 0;}`