Range XOR in Hashing and Tries

#1

Unable to pass testcases.
RANGE XOR
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
https://ide.codingblocks.com/s/66748

I Know there’s a editorial using tries, But want to know why I am even failing Bruteforce technique and also how the tries simplifies the solution?
Thanks.

1 Like
#2

Hi Lakshay, there are 2 errors in your code:

  1. Elements in your array can be 10^9 big so you have to use long long accordingly at required places.

  2. Your print maximum^k statement is misplaced. It should be inside the if(q==1) block, but is outside.

After you do these corrections your Brute Force will work correctly but it is beneficial to use Tries as its use along with binary search reduces the time complexity of program for an input as large as 10^9.

Hope this helps :slight_smile:

#3

Hey Lakshay,
As you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “ Ask Doubt ” section, when your doubt is resolved.

#4

@proRram Can you please explain the approach which uses Trie ? I am facing the same problem and can’t find the editorial in the online course. Can you help ?