Maximum XOR of Two Numbers in an Array

Description

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.

Hint

Train of Thought

建一个trie tree, 比较当前bit和trie里面对应的值有没有能亦或不为0的那个值不为空, 即当前值为0, 0^1 = 1, 找1, 当前为1, 1 ^ 1 = 0, 找0

Code

public class Solution {
    //TLE for very big data set

    // class Trie {
    //     Trie[] children;
    //     public Trie() {
    //         children = new Trie[2];
    //     }
    // }

    // public int findMaximumXOR(int[] nums) {
    //     if(nums == null || nums.length == 0) {
    //         return 0;
    //     }
    //     // Init Trie.
    //     Trie root = new Trie();
    //     for(int num: nums) {
    //         Trie curNode = root;
    //         for(int i = 31; i >= 0; i --) {
    //             int curBit = (num >>> i) & 1;
    //             if(curNode.children[curBit] == null) {
    //                 curNode.children[curBit] = new Trie();
    //             }
    //             curNode = curNode.children[curBit];
    //         }
    //     }
    //     int max = Integer.MIN_VALUE;
    //     for(int num: nums) {
    //         Trie curNode = root;
    //         int curSum = 0;
    //         for(int i = 31; i >= 0; i --) {
    //             int curBit = (num >>> i) & 1;
    //             if(curNode.children[curBit ^ 1] != null) {
    //                 curSum += (1 << i);
    //                 curNode = curNode.children[curBit ^ 1];
    //             }else {
    //                 curNode = curNode.children[curBit];
    //             }
    //         }
    //         max = Math.max(curSum, max);
    //     }
    //     return max;
    // }


    public int findMaximumXOR(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        // Init Trie.
        Object[] root = {null, null};
        for(int num: nums) {
            Object[] curNode = root;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >>> i) & 1;
                if(curNode[curBit] == null) {
                    curNode[curBit] = new Object[]{null, null};
                }
                curNode = (Object[]) curNode[curBit];
            }
        }
        int max = Integer.MIN_VALUE;
        for(int num: nums) {
            Object[] curNode = root;
            int curSum = 0;
            for(int i = 31; i >= 0; i --) {
                int curBit = (num >>> i) & 1;
                if(curNode[curBit ^ 1] != null) {
                    curSum += (1 << i);
                    curNode = (Object[]) curNode[curBit ^ 1];
                }else {
                    curNode = (Object[]) curNode[curBit];
                }
            }
            max = Math.max(curSum, max);
        }
        return max;
    }
}

Complexity