### Usu's blog

By Usu, history, 6 years ago,

Hey guys, I am returning to you with a problem. Given n numbers a1 a2.. an, find the substring (some consecutive nummbers) with the maximum xor string.

I know that we must use a trie, but I don't really know how. Can anybody explain me please?

• +1

 » 6 years ago, # |   0 Well if you want to find answer for some a[i] 0<=i
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Solution is n*log(max(a[i]))
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 If you mean how to implement trie check this submission, it may be helpful
•  » » » » 6 years ago, # ^ |   0 Turns out I'm wrong, forget about it.
•  » » » » » 6 years ago, # ^ |   0 But I have idea for alternate version, but I'm not sure if it will fit time limit. Can you give me site where I can submit my solution so I can tell if I'm right?
•  » » » » » » 6 years ago, # ^ |   0 I talked briefly with a friend about this, I wish I had a location for this problem
•  » » » » » » » 6 years ago, # ^ |   +1
 » 6 years ago, # |   +19 This problem can be solved using binary trie.First calculate the prefix xor of the array i.e. pre[0] = 0; pre[i] = pre[i — 1] ^ a[i]; (1 <= i <= n)Now we know that the xor sum of a range [l, r] will be pre[r] ^ pre[l — 1].So, firstly insert 0 in your trie. Now for each i in range [1, n], check for pre[i] the maximum xor pair that you can find out in your trie and let's call it t[i]. So, the answer will be max over all such pre[i] ^ t[i].By maximum xor pair of pre[i] i.e. t[i], I mean, the number such that among all the numbers that are inserted in the trie, pre[i] ^ (that number) should be maximum.How to find out t[i] ?It's actually very simple. Build a binary trie. Now, for finding the max xor pair, you need to go over all the bits of pre[i] starting from the Most Significant Bit and if it's set then we'll try to find a number(from trie), with this bit off, and if it's off, then we'll try to find a number with this bit on. Thus guaranteeing us the maximum xor pair.
 » 6 years ago, # |   0 Do a prefix xor on the array. A subarray in the previous context is now either a single element in this context, or a xor of 2 elements, and you want the maximum of those. We can find for each element in the array, another element in the array that gives maximal xor with it, and you can do it with a trie:Build a trie, where each number in the array is inserted by its bits, starting from the most significant to the least significant. Now suppose this trie is given an integer X and you want to find the best element in the trie to xor it with. Iterate over the bits of X from the most significant, and also keep the node T in the trie you're currently on (initially the root). if the next most significant bit is 1/0, then you want to check if T has any children from edge 0/1. If there is you go by that edge, otherwise you go by the opposite edge.So you do this with each element in the array, get the maximum of those and compare it with the maximum of the array.
 » 6 years ago, # |   +1 A related problem 617E - XOR and Favorite Number
 » 6 years ago, # |   0 Thank you all!
 » 6 years ago, # |   +1 Do checkout this one : Tutorial-on-Trie-and-example-problems
 » 6 years ago, # |   0