Unable to approach

#1

The problem is too tough for me.
Kindly help with the approach to solve it

#2

hi @tusharbajaj200153_02bc6c0c5583c81d,
u will be asked Q queries.

the queries can be of two type

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

type 0 -> where u need to insert the given number in the end of the array
type 1-> where u are given two index L and R and u need to any value Y from that range of array such that its xor with x is maximum.
solution ->
We can solve this problem using a trie data structure. 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 ,go in the other direction. To search if at least one index is within the stored indexes we will use binary search.

Reference Code

1 Like
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.