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.
Why is this faster?
You still need to add every element of the array to the tree in order to search the tree, which must take some time, whereas the obvious solution just xor's with each array element straight up. That is:
Obvious algorithm: just xor with each array element and see which is greatest.
More Optimal algorithm: add each array element to tree, then search the tree to find the max xor.
Why is the second significatntly more optimal? They both run in O(array.length), though I can see how perhaps the second is faster by a constant factor. Is that it or am I missing something?
Maximum Xor
You are viewing a single comment's thread. Return to all comments →
Why is this faster? You still need to add every element of the array to the tree in order to search the tree, which must take some time, whereas the obvious solution just xor's with each array element straight up. That is: Obvious algorithm: just xor with each array element and see which is greatest. More Optimal algorithm: add each array element to tree, then search the tree to find the max xor. Why is the second significatntly more optimal? They both run in O(array.length), though I can see how perhaps the second is faster by a constant factor. Is that it or am I missing something?