Hello sir/ma’am, my code for this problem is giving wrong output for the following test case: 8
0 3
0 5
0 10
0 6
1 1 4 6
0 7
0 9
1 1 4 6 , I am unable to figure out what’s wrong …could you please help? sharing my code: https://ide.codingblocks.com/s/223934 Also when i tried to submit this, wrong ans is coming for test cases 0 and 1.
Range Xor- Tries
@priyanshi.agarwal3405
we need to keep in mind that
- At each node of the trie, we will store the ith bit of the number for a query of type 0.
- To solve the query of type 1 we will store the indexes of the number that pass through that node.
- When we go down the tree during a query and maximizing the xor, we go in a direction that contains at least one index in range L to R, otherwise, we will go in the other direction.
- To search if at least one index is within the stored indexes we will use binary search.
(Since the indices will always be positive, you can apply count sort on them. That will do your work in linear time.)
Now, keeping above in mind, try to correct your code.
updated code
Ma’am i compared my code with yours, logic is same. The only mistake i found in my code was that i was passing wrong index array to binarySearch func. Now i have corrected that and the sample test case which i shared is now giving correct ans, but still 2 test cases are not passing. Please tell why is it so?
@priyanshi.agarwal3405
line 86 and 41
I have marked the changes in your code
mark your doubt as resolved if u are satisfied and rate me as well 
Ma’am, i am unable to understand why the change you made in line 86 has to be done. If current bit is 1, then we’ll look for 0 and if 0 exists then only value of curr_xor should be increased, otherwise we’ll settle for 1 and then curr_xor should not be increased. but acc to you we are increasing curr_xor if we find 1 , current bit also being 1. Is it not contradictory to what Prateek bhaiya told in video???
Hello ma’am, Please reply…