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.

 1 public class Solution {
 2     public int findMaximumXOR(int[] nums) {
 3         int mask = 0, max = 0;
 4         for (int i=31; i>=0; i--) {
 5             mask |= 1<<i;
 6             HashSet<Integer> prefixes = new HashSet<Integer>();
 7             for (int each : nums) {
 8                 prefixes.add(each & mask); // reserve Left bits and ignore Right bits
 9             }
10             int tmpMax = max | (1<<i);   
11             //possible new max, for example: max right now is 11000, then tmpMax=11100, max is 11100, tmpMax is 11110
12             for (int prefix : prefixes) {
13                 if (prefixes.contains(tmpMax^prefix)) 
14                     max = tmpMax;
15             }
16         }
17         return max;
18     }
19 }