Get the Maximum XOR of Two Numbers in an Array in Java

The challenge

Given a non-empty array of numbers, a, a₁, a₂, … , a_n-1, where 0 ≤ a_i < 2³¹.

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int findMaximumXOR(int[] nums) {
        // store our maximum
        int max = 0;
        
        // loop through all numbers
        for (int i=0; i<nums.length; i++) {
            // loop through all our numbers again
            for (int j=0; j<nums.length; j++) {
                // keep a temp of the XOR
                int tmp = nums[i] ^ nums[j];
                // check if it's bigger
                if (tmp>max) max = tmp;
            }
        }

        // return our maximum        
        return max;
    }
}

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.