I am trying to solve a well known problem called the Maximum XOR pair ina given range. If you are unaware about the probelm here is the prompt given to me:
You are given an array and Q queries of two types.
Type 0: Given a number x , insert the number at the last of the array.
Type 1: Given a number X and two integers L, R, Find a number Y in the range L, R to maximize X ^ Y
Input Format
First line of the test case will be the number of queries Q . Then on next Q subsequent lines you will be given a query either of type 0 or type 1. Query of type 0 is of the form : 0 X, where X is the integer to be inserted . Query of type 1 is of the form : 1 L R X
Constraints
0 <= element of array <= 10^9
1 <= N <= 10^5
Output Format
For each query of type 1 output the desired value.
Sample Input
5
0 3
0 5
0 10
0 6
1 1 4 6
Sample Output
10
I am using Tries to find out the maximum XOR for the given question my for some reason it gives a Run Time Error in 2 test cases. I am not sure why is that. Please help!
Here is my code:
#include<bits/stdc++.h>
using namespace std;
class node {
public:
int index;
node * left; // data = 0
node * right; // data = 1
};
class Trie {
node * root;
public:
Trie() {
root = new node();
}
void insert(int n, int idx) {
// ith bit of a number is (n >> i) & 1
node * temp = root;
for(int i = 31; i >= 0; i--) {
int bit = (n >> i) & 1;
if(bit == 0) {
if(temp->left == NULL) {
temp->left = new node();
temp->index = idx;
}
temp = temp->left;
}
else {
if(temp->right == NULL) {
temp->right = new node();
temp->index = idx;
}
temp = temp->right;
}
}
}
int max_xor_helper(long long int value, int L, int R) {
node * temp = root;
long long int current_ans = 0;
for(int j = 31; j >= 0; j--) {
int bit = (value >> j) & 1;
if(bit == 0) {
// finding complimentary value
if(temp->right != NULL and temp->index >= L and temp->index <= R) {
temp = temp->right;
current_ans += (1 << j); // 2 ^ j
}
else {
temp = temp->left;
}
}
else {
if(temp->left != NULL and temp->index >= L and temp->index <= R) {
temp = temp->left;
}
else {
temp = temp->right;
current_ans += (1 << j);
}
}
}
return current_ans;
}
};
int maxXORPair(Trie root, int L, int R, int X) {
// Trie root;
// int max_xor = 0, max_xor_partner = 0;
// for(int i = L; i <= R; i++) {
// int val = arr[i];
// root.insert(val);
// int curr_ans = root.max_xor_helper(X, L, R);
// if(curr_ans > max_xor) {
// max_xor_partner = curr_ans ^ val;
// max_xor = curr_ans;
// }
// }
return root.max_xor_helper(X, L, R);
}
int main() {
Trie root;
int idx = 0;
// vector<int> v;
int queries;
cin>>queries;
for(int i = 0; i < queries; i++) {
int type;
cin>>type;
if(type == 0) {
long long int val;
cin>>val;
root.insert(val, idx);
idx++;
// v.push_back(val);
}
else {
int L, R;
cin>>L>>R;
long long int X;
cin>>X;
long int ans = maxXORPair(root, L, R, X);
cout<<ans<<endl;
}
}
return 0;
}
See: https://www.learncpp.com/cpp-tutorial/null-pointers
Just like normal variables, pointers are not initialized when they are instantiated.
Initialize your pointers to NULL
.