In this HackerEarth Minimum XOR problem solution You are given Q queries of two types:
  1. X: Append value X into an array.
  2. X K: You are required to print the Kth minimum XOR of X with the current array.
You have to make a new array whose ith element is current_array[i]^x. Then sort it and print the Kth element.


HackerEarth Minimum XOR problem solution


HackerEarth Minimum XOR problem solution.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define ALL(x) x.begin(),x.end()
#define vec vector<int>
#define LG 63
#define int ll

typedef struct data
{
data* bit[2];
int below = 0;
}trie;

trie* head;

void insert(int x)
{
trie* cur = head;
int y = x;
for(int i=LG ;i>=0 ;i--)
{
ll t= (1ll << i );
int b = (x>>i) & 1;
cur -> below++ ;
if(!cur -> bit[b])
cur -> bit[b] = new trie();
cur = cur -> bit[b];
}
cur -> below++;
}

int query(int y,int k)
{
ll ans = 0;
trie* curr = head;

for(int i=LG;i>=0;i--)
{
ll t = ( 1ll << i );
int b = ( y >> i ) & 1;

ll ava=0;

if( curr -> bit[b] )
ava = curr -> bit[b] -> below;

if( ava >= k )
{
curr = curr -> bit[b];
}
else
{
ans += t;
k -= ava;
if( !curr -> bit[!b] )
curr -> bit[!b] = new trie();
curr = curr -> bit[!b];
}
}
return ans;
}

int32_t main()
{

head=new trie();

ll q;
cin >> q;

while(q--)
{
ll t;
cin>>t;

if(t==1)
{
ll x;
cin >> x;
insert(x);
}
else
{
ll x,k;
cin >> x >> k;
cout<<query(x,k)<<"\n";
}
}
}