Three Solutions to Solve This Problem With O(n) Complexity
1.  using bit manipulation and HashMap [beats 67%]\nThe xor operation has a good feature, a^b=c then c^a=b, c^b=a;\nSince the range of num is 0<=num<2^31, the m
**1.  using bit manipulation and HashMap [beats 67%]**\nThe xor operation has a good feature, a^b=c then c^a=b, c^b=a;\nSince the range of num is 0<=num<2^31, the max xor value should have the first 1 as high as possible in binary representation.\nSo we can find the max greedy.  \nAssume the largest xor value(tmp) has 1 in ith position. [i from 31 to 0]\nGenerate the prefix for all num in array, and store them in a set. Then we check all prefixes whether they can xor another prefix to get tmp. If we got the tmp, set the max = tmp. With a set we can get the answer with O(n) complexity\nIn total, this algorithm has O(32n) = O(n) time complexity, and O(n) space complexity.\n```\nclass Solution {\n    public int findMaximumXOR(int[] nums) {\n        int max = 0, mask = 0;\n        for(int i = 31; i >= 0; i--){\n            mask = mask | (1 << i);\n            Set<Integer> set = new HashSet<>();\n            for(int num : nums){\n                set.add(num & mask);\n            }\n            int tmp = max | (1 << i);\n            for(int prefix : set){\n                if(set.contains(tmp ^ prefix)) {\n                    max = tmp;\n                    break;\n                }\n            }\n        }\n        return max;\n    }\n}\n```\n2.  build a trie tree and find max xor value for each number, then get the maximum XOR in this array [beats 93%]\nWe can build a trie tree for this array with binary expression. The tree\'s height is 32, left means 0, right means 1, the level of node means its index in num\'s binary expression.\nThen let evey num match the trie tree to get the maximum xor value. It\'s also greedy. If we have 0 in ith subscript, if right node is not null, we match right node, so do the 1.\nWe use a max variable to get the max xor value when traversing the num.\nTime Complexity O(n)+O(32n) = O(n)\n```\nclass TrieNode {\n    boolean is_leaf = false;\n    TrieNode left;\n    TrieNode right;\n\n    public TrieNode(boolean is_leaf, TrieNode left, TrieNode right) {\n        this.is_leaf = is_leaf;\n        this.left = left;\n        this.right = right;\n    }\n\n    public TrieNode() {\n    }\n\n    public TrieNode(TrieNode left, TrieNode right) {\n        this.left = left;\n        this.right = right;\n    }\n}\n\nclass Solution {\n     public int findMaximumXOR(int[] nums) {\n        TrieNode root = buildTrieTree(nums);\n        int maxNum = 0;\n        for (int i = 0; i < nums.length; i++) {\n            int xorValue = 0;\n            TrieNode cur = root;\n            for (int j = 31; j >= 0; j--) {\n                boolean flag = getBit(nums[i], j);\n                // \u5F53\u524D\u4E3A0\uFF0C\u770B\u5F53\u524D\u8282\u70B9\u662F\u5426\u6709\u4E3A1\u7684\u5B50\u8282\u70B9\n                if (!flag) {\n                    if (cur.right != null) {\n                        xorValue += (1 << j);\n                        cur = cur.right;\n                    } else\n                        cur = cur.left;\n                }else {// \u5F53\u524D\u4E3A1 \uFF0C\u5C3D\u53EF\u80FD\u5339\u914D\u4E3A0\u7684\u5B50\u8282\u70B9\n                    if (cur.left != null) {\n                        xorValue += (1 << j);\n                        cur = cur.left;\n                    } else\n                        cur = cur.right;\n                }\n            }\n            maxNum = Math.max(xorValue, maxNum);\n        }\n        return maxNum;\n    }\n\n    public TrieNode buildTrieTree(int[] nums) {\n        TrieNode root = new TrieNode();\n        for (int i = 0; i < nums.length; i++) {\n            insert(root, nums[i]);\n        }\n        return root;\n    }\n\n    public void insert(TrieNode root, int num) {\n        for (int i = 31; i >= 0; i--) {\n            if (!getBit(num, i)) {\n                if (root.left == null)\n                    root.left = new TrieNode();\n                root = root.left;\n            } else {\n                if (root.right == null)\n                    root.right = new TrieNode();\n                root = root.right;\n            }\n        }\n    }\n\n    private boolean getBit(int num, int i) {\n        return (num & (1 << i)) != 0;\n    }\n}\n```\n3.  build a trie tree and find maximum xor value by recursing the tree [beats 99%]\nSince we store every num in the trie tree. So there must be a way to get the max xor value in this trie tree.\nFor each non-leaf node, it must have a subnode,whether left of right.\nSo for current node left, right. if ll&&rr is not null or lr&&rl is not null, we greedy select this two subnode, get the max xor value of f(ll,rr) and f(lr,rl) . if not we select the max value of f(ll,rl)and f(lr,rr)  \n[ll=left.left,lr=left.right,so do others...]\nBuild the trie tree O(n), get max value O(1) by recursing the trie tree, So in total, time complexity is O(n)\n```\nclass TrieNode {\n    boolean is_leaf = false;\n    TrieNode left;\n    TrieNode right;\n\n    public TrieNode(boolean is_leaf, TrieNode left, TrieNode right) {\n        this.is_leaf = is_leaf;\n        this.left = left;\n        this.right = right;\n    }\n\n    public TrieNode() {\n    }\n\n    public TrieNode(TrieNode left, TrieNode right) {\n        this.left = left;\n        this.right = right;\n    }\n}\n\nclass Solution {\n     public int findMaximumXOR(int[] nums) {\n        TrieNode root = buildTrieTree(nums);\n        int level = 31;\n        TrieNode cur = root;\n        int ans = 0;\n        while (cur != null && (cur.left == null || cur.right == null)) {\n            cur = cur.left == null ? cur.right : cur.left;\n            level--;\n        }\n         if(cur!=null){\n              ans = (1 << level);\n            ans += dfs(cur.left, cur.right, level);\n             }\n        return ans;\n    }\n    public int dfs(TrieNode left, TrieNode right, int level) {\n        int max = 0;\n        level--;\n        TrieNode ll = left.left, lr = left.right, rl = right.left, rr = right.right;\n        if (ll != null && rr != null || lr != null && rl != null) {\n            max += (1 << level);\n            int t1 = 0, t2 = 0;\n            if (ll != null && rr != null)\n                t1 = dfs(ll, rr, level);\n            if (lr != null && rl != null)\n                t2 = dfs(lr, rl, level);\n            max = max + Math.max(t1, t2);\n\n        } else {\n            int t1 = 0, t2 = 0;\n            if (ll != null && rl != null)\n                t1 = dfs(ll, rl, level);\n            if (lr != null && rr != null)\n                t2 = dfs(lr, rr, level);\n            max = Math.max(t1, t2);\n        }\n        return max;\n    }\n\n    public TrieNode buildTrieTree(int[] nums) {\n        TrieNode root = new TrieNode();\n        for (int i = 0; i < nums.length; i++) {\n            insert(root, nums[i]);\n        }\n        return root;\n    }\n\n    public void insert(TrieNode root, int num) {\n        for (int i = 31; i >= 0; i--) {\n            if (!getBit(num, i)) {\n                if (root.left == null)\n                    root.left = new TrieNode();\n                root = root.left;\n            } else {\n                if (root.right == null)\n                    root.right = new TrieNode();\n                root = root.right;\n            }\n        }\n    }\n\n    private boolean getBit(int num, int i) {\n        return (num & (1 << i)) != 0;\n    }\n}\n```
[]