Trie Interview problem

#1

My approach was that I formed a prefix or array and find the maximum xor pair (let’s say pair1), and their indexes. now for second xor pair, it can lie either left of the pair1 or right of the pair1.
so I formed a separate trie for indexes left of pair1 and for indexes right of pair1.

I think it can be optimized, I am unable to think the different approach and is my approach even correct?

#2

Hey @abhir26
Just think of it this way
At any given index, you need max xor sum on left and max xor sum on right
So just make 2 arrays one for max prefix and other for max suffix
Then at each index just add sum of max prefix and max suffix
Best of luck !!

Please close the doubt is your query is resolved

#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.

#4

Didn’t understand the approach. How can we solve this question with tries?

#5
  1. int result = 0;
  2. Traverse the array, let say we are at index “i”, we consider index “i” to be the end of the first range
  3. Get the maximum sub array xor for elements upto index “i”, sub array ending at index “i” (Let it be x1)
    // This part is simply the maximum XOR subarray question
  4. Implement some function say “GetRightXORMax” which return the maximum sub array xor from index “i + 1” to end of the array (Let it be x2) // This function should be implemented in O(1) time complexity.
  5. if(x1 + x2 > result) {
  6. result = x1 + x2
  7. }
  8. print result;