How the finding a pair with maximum xor from cumulative xor array in the last of the lecture will take O(N) time? I think it will take O(N^2) time to find two number with maximum xor

#1

I think we need to run 2 loops to find the pair from the cumulative xor array so that the xor of those two number is maximum…

#2

hello @abhi542136

time complexity will depend on the approach.
i am not sure which lecture u r talking about.

but if in that they are using two nested loop then time complexity is O(N^2)
otherwise if they are using trie then time complexity is O(N)

#3

I am talking about trie 05 - Subarray with maximum xor lecture…
So can you just write the code of how to find a pair of number from cumulative xor array with maximum xor using Trie Data Structure… just give me a hint, I will understand

#4

…

insert all prefix xor in ur trie.
and then find what is maximum xor with thew help of that trie
check this->

1 Like
#5

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.