Get the Maximum XOR of Two Numbers in an Array in Java
The challenge
Given a nonempty array of numbers, a_{}, a_{1}, a_{2}, … , a_{n1}, where 0 ≤ a_{i} < 2^{31}.
Find the maximum result of a_{i} XOR a_{j}, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28.
The solution in Java
We can very quickly resolve this challenge by performing a double loop and comparing our resultant:


While this solution does come to a correct answer, it is not in the O(n)
of time due to our second loop, and our space complexity could be made better by not using an additional variable.