We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I'll assume the non-efficient solution is obvious for most people.
rene_d's hint about using a Trie is key here, as it's critical for getting O(n) efficiency out of the problem.
I had never encountered a Trie before, so I had to grabble with it a bit before it made intuitive sense here.
If you look up how a bitwise Trie is structured, you'll get an idea that it's a binary tree where each 1 or 0 bit at each position in a given integer points to another node. If you were to draw out any given value in a binary tree, you'd follow all 32-bits down, with 0 bits going left and 1 bits going right, until you reached a leaf node, and then you'd find the value you are searching for.
If you take the input array of this problem and build a Trie out of all of the values in the array, you'd get a large tree with lots of values branching off from the various bit positions.
How that helps you solve the maximum XOR problem is that you can do a query in the Trie to help you find what best possible XOR out of the possible choices.
What's the best possible XOR companion value? It's one where all of the bits are the exact opposite of the candidate value.
For example, if your query value (let's use nibbles for this discussion for conciseness) has a bit pattern of 0010, then the best possible XOR companion value would be 1101, which would give you a result of 1111.
With a Trie query, you can see if there's a branch at the opposite bit value at each bit position. In the example above, for the MSB of 4, you'd try and see if there was a branch with a bit value of 1; in this case there is, but if not then you would take the branch with a bit value of 0 since that path actually exists.
The end result is that you can query the Trie quickly and find the best possible match for every single query.
Maximum Xor
You are viewing a single comment's thread. Return to all comments →
This was a fun problem.
I'll assume the non-efficient solution is obvious for most people.
rene_d's hint about using a Trie is key here, as it's critical for getting O(n) efficiency out of the problem.
I had never encountered a Trie before, so I had to grabble with it a bit before it made intuitive sense here.
If you look up how a bitwise Trie is structured, you'll get an idea that it's a binary tree where each 1 or 0 bit at each position in a given integer points to another node. If you were to draw out any given value in a binary tree, you'd follow all 32-bits down, with 0 bits going left and 1 bits going right, until you reached a leaf node, and then you'd find the value you are searching for.
If you take the input array of this problem and build a Trie out of all of the values in the array, you'd get a large tree with lots of values branching off from the various bit positions.
How that helps you solve the maximum XOR problem is that you can do a query in the Trie to help you find what best possible XOR out of the possible choices.
What's the best possible XOR companion value? It's one where all of the bits are the exact opposite of the candidate value.
For example, if your query value (let's use nibbles for this discussion for conciseness) has a bit pattern of 0010, then the best possible XOR companion value would be 1101, which would give you a result of 1111.
With a Trie query, you can see if there's a branch at the opposite bit value at each bit position. In the example above, for the MSB of 4, you'd try and see if there was a branch with a bit value of 1; in this case there is, but if not then you would take the branch with a bit value of 0 since that path actually exists.
The end result is that you can query the Trie quickly and find the best possible match for every single query.