Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Minimum XOR problem solution

YASH PAL, 31 July 2024
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";
}
}
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes