JAVA Easy to Understand Solution + explained!!!! O(n)    ( Trie )
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91059/Java-O(n)-solution-using-Trie\nclass Solution {\n    \n    // binary trie, wh
[https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91059/Java-O(n)-solution-using-Trie](http://)\nclass Solution {\n    \n    // binary trie, where each trie node has only 2 child \n    // one child will represent bit "1" in the binary representation of num\n    // one child will represent bit "0" in the binary representation of num\n    private static class TrieNode {\n        // children[0]: represent bit "1" in the binary representation \n        // children[1]: represent bit "0" in the binary representation \n        private final TrieNode[] children;\n        \n        private TrieNode() {\n            children = new TrieNode[2];\n        }\n    }\n    \n    private TrieNode root;\n    \n    public int findMaximumXOR(int[] nums) {\n        // initialize the root node\n        root = new TrieNode();\n        \n        TrieNode curr;\n        \n        // build the trie \n        for (int num : nums) {\n            // starting from root;\n            curr = root;\n            \n            // since every num is positive, their 31th bit is always 0\n            // we can ignore that bit and directy build from the 30th bit \n            for (int i = 30; i >= 0; --i) {\n                int bit = getIthBit(num, i);\n                \n                // if current bit is 0, it will go to children[1]\n                // if current bit is 1, it will go to children[0]\n                if (curr.children[bit ^ 1] == null) {\n                    curr.children[bit ^ 1] = new TrieNode();\n                }\n                \n                curr = curr.children[bit ^ 1];\n            }\n        }\n        \n        int ans = Integer.MIN_VALUE;\n        \n        // iterate through each num again\n        // starting from those significant bits of num, we try the best \n        // to go to the node that represent the negation of current bit \n        // if such node doesn\'t exist, we have to go the node that represents\n        // the current bit \n        for (int num : nums) {\n            // starting from root\n            curr = root;\n            \n            // keep track of the maximum result of XOR current num with \n            // other num in the array\n            int rst = 0;\n            for (int i = 30; i >= 0; --i) {\n                int bit = getIthBit(num, i);\n                \n                // check to see if node that represents the negation of \n                // current bit exists or not. If exists, go to that way \n                \n                // if current bit is 1, then we want to go to children[1] (which represents 0)\n                // if current bit is 0, then we want to go to children[0] (which represents 1)\n                if (curr.children[bit] != null) {\n                    curr = curr.children[bit];\n                    \n                    // if exists, then we will have a "1" at the current index\n                    // in the result of maximum XOR \n                    rst += (1 << i);\n                } \n                // if not exists\n                else {\n                    curr = curr.children[bit ^ 1];\n                }\n            }\n            \n            // keep track of global maximum \n            ans = Math.max(ans, rst);\n            // there is no need to continue when final result has reached max value \n            if (ans == Integer.MAX_VALUE) break;\n        }\n        \n        return ans;\n    }\n    \n    // get the ith bit (count from LSB, 0-based) of num\n    private int getIthBit(int num, int i) {\n        return (num & (1 << i)) == 0 ? 0 : 1;\n    }\n}\n```
['Java']