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

The challenge

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ ij < n.

Could you do this in O(n) runtime?


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:

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.

Notify of
Inline Feedbacks
View all comments