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 ≤ 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:
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.