➤ Problem Link : 706D. Vasiliy's Multiset
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
struct TrieNode{
TrieNode *arr[2];
int cnt;
ll value;
TrieNode(){
arr[0]=NULL;
arr[1]=NULL;
cnt=0;
}
};
void insert(TrieNode *root, ll val)
{
// cout<<val<<" ";
TrieNode *curr=root;
ll a;
for(ll v=31;v>=0;v--)
{
a=((val/(ll)pow(2,v)) % 2);
a=a%2;
// cout<<a;
if(curr->arr[a]==NULL)
curr->arr[a]=new TrieNode;
curr=curr->arr[a];
}
//cout<<endl;
curr->cnt++;
curr->value=val;
}
bool remove(TrieNode *curr, ll val, ll v)
{
if(v==-1)
{
// cout<<"done\n";
curr->cnt--;
if(curr->cnt==0)
return 1;
return 0;
}
ll a=((val/(ll)pow(2,v)) % 2);
a=a%2;
bool b = remove(curr->arr[a],val,v-1);
if(b)
{
delete curr->arr[a];
curr->arr[a]=NULL;
if(curr->arr[a^1]==NULL)
return 1;
}
return 0;
}
ll find(TrieNode * root, ll val)
{
TrieNode * curr = root;
ll a;
// cout<<val<<endl;
for(ll v=31;v>=0;v--)
{
a=((val/(ll)pow(2,v)) % 2);
a^=1;
if(curr->arr[a]!=NULL)
{
// cout<<a;
curr=curr->arr[a];
}
else
{
// cout<<"2";
curr=curr->arr[a^1];
}
}
return curr->value ^ val;
}
int main()
{
TrieNode * root = new TrieNode;
insert(root,0);
char c;
int q;
ll x;
cin>>q;
while(q--)
{
cin>>c>>x;
if(c=='+')
insert(root,x);
else if(c=='-')
remove(root,x,31);
else
cout<<find(root,x)<<"\n";
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.