i did not understood the intuition well…please help me in understanding that
Trie max xor(intuition)
Hello @Gaurav_dev, this is one of the famous problem which can be done using tries.
See what we need to do is to create a trie that will handle the binary nos. as we need to convert the nos. in the binary form.
And we can say tha no. having the largest MSB is the largest no. we can get. So we can now traverse the array and read the element one by one. So we can pick the element and we will check what is the maximum no. till now we can get from the tries so that our ans will be maximised. And after that we will store that no. into the trie.
So for checking we know in case of xor if we want to get the max element we need to get the maximum nos. of 1 in the binary form. So suppose if currently we have a no. and for any ith bit if it is 1 then we will check if there is any 0th bit at this position if there is we will choose this path as this will give 1 as the final bit ( as one bit is 1 and one bit is 0) and if we get 0 as the current ith bit then we will search that if there is any 1 set bit or not. In either of the cases if the desired bit is not there then we are restricted to follow the same bit path and that bit will be 0.
I hope the logic is clear to you, in case still there is any confusion pls let me know.
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.