sir why my code not work
Range xor problem
sir please reply i eanted to know my mistake
Hi @YASHMATHURIA123
As far as i can understand and relate your code, in valid() function, you are trying include that bit in your answer and checking if after including that bit my answer is still in the range l to r. But the problem in this approach is, as the elements are inserted bit by bit, so lets suppose you have included something in your answer. Then lets suppose variable ‘b’ is right now equal to R (range from L to R). So then after that point you can’t include other bits because it will be more that R.
But as you may be in the middle of Trie, so it is possible that all the remaining nodes till end are ‘1’ i.e. all are set bits. Then in that case you can’t take that answer.
All the things i said above is just to make you understand what you are doing wrong.
But your approach is wrong.
Also in this question for query of type 1, L and R are index of the array built from queries of type-0. Also the indexes L and R 1-based indexed, so you will need to take care that as well.
So the correct approach for this question should be, for query-0 while inserting the integer into the trie also include index(of this number) in the nodes of trie through which this integer goes while inserting in the trie.
So 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 ,go in the other direction. To search if at least one index is within the stored indexes we will use binary search.
I hope this helps.