Java | Binary Trie | Explained
Idea:\n A binary number is maximized by having max set (1) bits\n XOR result is 1 if bits are opposite else 0. This means the maximum result will be achieved wi
**Idea:**\n* A binary number is maximized by having max set (1) bits\n* XOR result is 1 if bits are opposite else 0. This means the maximum result will be achieved with operands a and b when a and b have the maximum number of opposite bits at the most significant places (as left as possible). Such a pair will give max XOR result\n* So for each query, we need to find the best possible match available stepping down bit by bit. This can be done most efficiently with a Trie\n* To search in trie, we need to know what is the max possible XOR for any number (say a). Ideally we\'d want max result to be `Integer.MAX_VALUE`. We\'ll use [XOR properties](https://accu.org/journals/overload/20/109/lewin_1915/) to find the operand\n```\na ^ b = Integer.MAX_VALUE\n=> b ^ a = Integer.MAX_VALUE           (Commutative property)\n=> b ^ a ^ a = Integer.MAX_VALUE ^ a   (Apply XOR a both sides) \n=> b ^ (a ^ a) = Integer.MAX_VALUE ^ a (Associative property)\n=> b ^ 0 = Integer.MAX_VALUE ^ a       (Self Inverse property)\n=> b = Integer.MAX_VALUE ^ a           (Identity Element property)\n\nso for maximum possible result, we need to XOR a with Integer.MAX_VALUE ^ a\n```\n* Create a trie and insert all the numbers in it. \n* This trie will have depth = 31 since we have ints which are of 31 value bits + 1 sign bit. Ignore the sign bit. Also notice that this is a binary tree with left (zero) and right (one) children nodes \n* Query:\n\t* Isolate each bit using a mask\n\t* If the bit is 0 and\n\t\t* current node has a `one/right` child, it means this is a 1 bit, so include this bit in the answer. Move to this node.\n\t\t* current node doesn\'t have `one` child , then move to the `zero/left` child\n\t* Vice versa if bit is 1\n\t \n![image](https://assets.leetcode.com/users/images/74b4d4ae-ef0a-48e8-87fc-e98d8e733966_1643282166.397064.png) \n>**T/S:** O(n)/O(1), where n = size(nums)\n```\npublic int findMaximumXOR(int[] nums) {\n\tvar trie = new Trie();\n\tArrays.stream(nums)\n\t\t  .forEach(trie::insert);\n\n\tvar max = 0;\n\tfor (var num : nums)\n\t\tmax = Math.max(max, num ^ trie.query(Integer.MAX_VALUE ^ num));\n\treturn max;\n}\n\nprivate static class Trie {\n\n\tprivate static final int[] MASKS = new int[31];\n\tprivate static class Node {\n\t\tprivate Node zero;\n\t\tprivate Node one;\n\t}\n\t\n\tprivate final Node root = new Node();\n\t\n\tstatic {\n\t\tIntStream.range(0, 31)\n\t\t\t\t .forEach(i -> MASKS[i] = 1 << i);\n\t}\n\n\tpublic Trie() {}\n\n\tpublic void insert(int n) {\n\t\tvar bitIndex = 30;\n\t\tvar current = root;\n\n\t\twhile (bitIndex >= 0) {\n\t\t\tvar bit = (MASKS[bitIndex--] & n) == 0 ? 0 : 1;\n\n\t\t\tif (bit == 0) {\n\t\t\t\tif (current.zero == null)\n\t\t\t\t\tcurrent.zero = new Node();\n\t\t\t\tcurrent = current.zero;\n\t\t\t} else {\n\t\t\t\tif (current.one == null)\n\t\t\t\t\tcurrent.one = new Node();\n\t\t\t\tcurrent = current.one;\n\t\t\t}\n\t\t}\n\t}\n\n\tprivate int query(int n) {\n\t\tvar bitIndex = 30;\n\t\tvar current = root;\n\t\tvar result = 0;\n\n\t\twhile (bitIndex >= 0) {\n\t\t\tvar bit = (n & MASKS[bitIndex]) == 0 ? 0 : 1;\n\n\t\t\tif (bit == 0) {\n\t\t\t\tif (current.zero == null) {\n\t\t\t\t\tcurrent = current.one;\n\t\t\t\t\tresult |= MASKS[bitIndex];\n\t\t\t\t} else {\n\t\t\t\t\tcurrent = current.zero;\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tif (current.one == null) {\n\t\t\t\t\tcurrent = current.zero;\n\t\t\t\t} else {\n\t\t\t\t\tcurrent = current.one;\n\t\t\t\t\tresult |= MASKS[bitIndex];\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tbitIndex--;\n\t\t}\n\n\t\treturn result;\n\t}\n}\n```\n***Please upvote if this helps***
['Trie', 'Java']