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.

Solution

public class Solution {
    public class TrieNode{
        public TrieNode left;
        public TrieNode right;
        public int val;
    }

    TrieNode root = new TrieNode();
    int ans = 0;

    public void build(int num) {
        TrieNode iter = root;
        for(int i = 31; i >= 0; i--) {
            if((num & (1 << i)) == 0) {
                if(iter.left == null) iter.left = new TrieNode();
                iter = iter.left;
            } else {
                if(iter.right == null) iter.right = new TrieNode();
                iter = iter.right;
            }
        }
        iter.val = num;
    }

    public void search(TrieNode one, TrieNode two) {
        if(one.left == null && one.right == null) {
            ans = Integer.max(ans, one.val ^ two.val);
            return;
        }
        if(one.left != null && two.right != null) search(one.left, two.right);
        if(one.right != null && two.left != null) search(one.right, two.left);
        if(one.left == null && two.left == null) search(one.right, two.right);
        if(one.right == null && two.right == null) search(one.left, two.left);
    }

    public int findMaximumXOR(int[] nums) {
        if(nums.length < 1) return 0;
        for(int num: nums) build(num);
        search(root, root);
        return ans;
    }
}