a few solutions
January 27th, 2022:\n\nKotlin\n\ndata class Node(var m: MutableMap<Int, Node> = mutableMapOf<Int, Node>())\nclass Solution {\n    fun findMaximumXOR(A: IntArray
**January 27<sup>th</sup>, 2022:**\n\n*Kotlin*\n```\ndata class Node(var m: MutableMap<Int, Node> = mutableMapOf<Int, Node>())\nclass Solution {\n    fun findMaximumXOR(A: IntArray): Int {\n        var best = 0\n        var m = Node()\n        for (x in A) {\n            var cand = 0\n            var (cur, alt) = Pair(m, m)\n            for (i in 31 downTo 0) {\n                var p = if (x and (1 shl i) != 0) 1 else 0\n                var q = p xor 1\n                if (!cur.m.contains(p))\n                    cur.m[p] = Node()\n                cur = cur.m[p]!!\n                if (alt.m.contains(q)) {\n                    alt = alt.m[q]!!; cand = cand xor (1 shl i)\n                } else {\n                    alt = alt.m[p]!!\n                }\n            }\n            best = Math.max(best, cand)\n        }\n        return best\n    }\n}\n```\n\n*Javascript*\n```\nlet findMaximumXOR = (A, m = new Map(), best = 0) => {\n    for (let x of A) {\n        let cand = 0;\n        let cur = m,\n            alt = m;\n        for (let i = 31; 0 <= i; --i) {\n            let p = x & (1 << i) ? 1 : 0,\n                q = p ^ 1;\n            if (!cur.has(p))\n                cur.set(p, new Map());\n            cur = cur.get(p);\n            if (alt.has(q))\n                alt = alt.get(q), cand ^= 1 << i;\n            else\n                alt = alt.get(p);\n        }\n        best = Math.max(best, cand);\n    }\n    return best;\n};\n```\n\n*Python3*\n```\nclass Solution:\n    def findMaximumXOR(self, A: List[int], best = 0) -> int:\n        m = {}\n        for x in A:\n            cand = 0\n            cur, alt = m, m\n            for i in range(31, -1, -1):\n                p = 1 if x & (1 << i) else 0\n                q = p ^ 1\n                if p not in cur: cur[p] = {}\n                cur = cur[p]\n                if q in alt:\n                    alt = alt[q]; cand ^= 1 << i\n                else:\n                    alt = alt[p]\n            best = max(best, cand)\n        return best\n```\n\n*C++*\n```\nstruct Node;\nusing NodePtr = shared_ptr<Node>;\nstruct Node {\n    using Map = unordered_map<int, NodePtr>;\n    Map m;\n};\nclass Solution {\npublic:\n    using VI = vector<int>;\n    int findMaximumXOR(VI& A, NodePtr root = make_shared<Node>(), int best = 0) {\n        for (auto x: A) {\n            auto cand = 0;\n            auto cur = root,\n                 alt = root;\n            for (auto i{ 31 }; 0 <= i; --i) {\n                auto p = x & (1 << i) ? 1 : 0,\n                     q = p ^ 1;\n                if (cur->m.find(p) == cur->m.end())\n                    cur->m[p] = make_shared<Node>();\n                cur = cur->m[p];\n                if (alt->m.find(q) != alt->m.end())\n                    alt = alt->m[q], cand ^= 1 << i;\n                else\n                    alt = alt->m[p];\n            }\n            best = max(best, cand);\n        }\n        return best;\n    }\n};\n```\n\n---\n\n**September 17<sup>th</sup>, 2020:**\n\nCreate a `\uD83C\uDF32` trie from the binary representation of each value `x` in `A`.  Our goal is to find the maximum xor of two values in `A`, thus we construct the trie starting from the left-most bit of each value `x`, ie. the most significant bit which results in the largest value, because we want to `\uD83D\uDCB0` greedily diverge an alternative path `alt` from the current path `cur` as soon as possible and whenever possible to construct the maximal `xor` in O(N) time.\n\nLet `cur` be the current path of the trie insertions for `x` and let `alt` be a pre-existing alternative path of the trie which greedily diverges from `cur` at the most significant bit possible.  Thus, the logic for updating `cur` and `alt` per trie traversal starting at `root` is as follows:\n\n* **`\uD83D\uDC40` Current Path:** insert trie nodes as needed otherwise follow the pre-existing current path\n* **`\uD83E\uDD14` Alternative Path:** greedily diverges from current path whenever possible to formulate the max `xor`, otherwise follow the pre-existing current path\n\n**Notes:**\n* Upon each successful alternative path divergence, the ongoing best `xor`\'s bit is set at that `i`<sup>th</sup> position\n* I chose `p` and `q` to represent opposite bit values because these characters look "opposite" to me, ie. the "hump" in `p` "points" to-the-right `\uD83D\uDC49` whereas the "hump" in `q` "points" to-the-left `\uD83D\uDC48`\n* This is probably one of the most difficult "medium" questions I\'ve solved.  I solved this from scratch today (2020-09-16) as part of the September coding challenge, and it took me about an hour.  However, I previously solved this problem 3 years ago with help from [@jill-brocli\'s solution here](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91056/C%2B%2B-Trie-with-explanation), so I\'ve added detailed notes from 3 years ago in the "supplemental" section at the very bottom.  I hope those additional details are helpful in case the description above doesn\'t make sense\uD83D\uDC4D\n\n---\n\n*Javascript*\n```\nlet findMaximumXOR = (A, max = 0) => {\n    let root = {};                                 // \uD83C\uDF32 trie\n    for (let x of A) {\n        let xor = 0;\n        let cur = root,                            // \uD83D\uDC40 current path in trie for inserting binary representation of x\n            alt = root;                            // \uD83E\uDD14 alternative path for pre-existing values in trie\n        for (let i = 31; 0 <= i; --i) {\n            let p = 0 < (x & (1 << i)) ? 1 : 0,    // \uD83D\uDE99 direction p and opposite \uD83D\uDE97 direction q\n                q = p ^ 1;\n            cur = cur[p] = cur[p] || {};           // \uD83D\uDE99 add direction p to \uD83D\uDC40 current path (as needed)\n            if (alt[q])\n                alt = alt[q], xor ^= (1 << i);     // \uD83D\uDE97 diff direction q for \uD83E\uDD14 alternative path (\uD83D\uDCB0 greedily take this path whenever possible)\n            else\n                alt = alt[p];                      // \uD83D\uDE99 same direction p for \uD83E\uDD14 alternative path\n        }\n        max = Math.max(max, xor);                  // \uD83C\uDFAF max xor\n    }\n    return max;\n};\n```\n\n*Python3*\n```\nclass Solution:\n    def findMaximumXOR(self, A: List[int], best = 0) -> int:\n        root = {}                                      # \uD83C\uDF32 trie\n        for x in A:\n            xor = 0\n            cur = root                                 # \uD83D\uDC40 current path in trie for inserting binary representation of x\n            alt = root                                 # \uD83E\uDD14 alternative path for pre-existing values in trie\n            for i in range(31, -1, -1):\n                p = 1 if 0 < (x & (1 << i)) else 0     # \uD83D\uDE99 direction p and opposite \uD83D\uDE97 direction q\n                q = p ^ 1\n                cur[p] = cur[p] if p in cur else {}    # \uD83D\uDE99 add direction p to \uD83D\uDC40 current path (as needed)\n                cur = cur[p]\n                if q in alt:                           # \uD83D\uDE97 diff direction q for \uD83E\uDD14 alternative path (\uD83D\uDCB0 greedily take this path whenever possible)\n                    alt = alt[q]; xor ^= (1 << i)\n                else:                                  # \uD83D\uDE99 same direction p for \uD83E\uDD14 alternative path\n                    alt = alt[p]\n            best = max(best, xor)                      # \uD83C\uDFAF max xor\n        return best\n```\n\n*C++*\n```\nclass Solution {\npublic:\n    using VI = vector<int>;\n    struct Trie {\n        unordered_map<int, shared_ptr<Trie>> m;\n    };\n    int findMaximumXOR(VI& A, int max = 0) {\n        auto root = make_shared<Trie>();                 // \uD83C\uDF32 trie\n        for (auto x: A) {\n            auto _xor{ 0 };\n            auto cur{ root },                            // \uD83D\uDC40 current path in trie for inserting binary representation of x\n                 alt{ root };                            // \uD83E\uDD14 alternative path for pre-existing values in trie\n            for (auto i{ 31 }; 0 <= i; --i) {\n                auto p = 0 < (x & (1 << i)) ? 1 : 0,     // \uD83D\uDE99 direction p and opposite \uD83D\uDE97 direction q\n                     q = p ^ 1;\n                if (cur->m.find(p) == cur->m.end())      // \uD83D\uDE99 add direction p to \uD83D\uDC40 current path (as needed)\n                    cur->m[p] = make_shared<Trie>();\n                cur = cur->m[p];\n                if (alt->m.find(q) != alt->m.end())      // \uD83D\uDE97 diff direction q for \uD83E\uDD14 alternative path (\uD83D\uDCB0 greedily take this path whenever possible)\n                    alt = alt->m[q], _xor ^= (1 << i);\n                else                                     // \uD83D\uDE99 same direction p for \uD83E\uDD14 alternative path\n                    alt = alt->m[p];\n            }\n            max = std::max(max, _xor);                   // \uD83C\uDFAF max xor\n        }\n        return max;\n    }\n};\n```\n\n---\n\n**Supplemental:** these are my notes from 3 years ago...\n\nhttps://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91056/C%2B%2B-Trie-with-explanation\n\nHi @jill-brocli, thanks so much for sharing this easy to understand code!  I have written a solution in C++11 with inspiration from your solution.  For folks having a hard time ( like me ) understanding this problem and the various solutions, I found it helpful to step through the below code after changing the ```MAX_BIT_POS``` to 3 in order to ensure the proper max xor is calculated for small numbers less than 16.\n\n**Here\'s how this solution works:**\n\nLet\'s assume for simplicity that we have changed ```MAX_BIT_POS``` to 3, and that our vector contains the integers [ 6, 8, 10 ].\n\n```\n   3210 (bit position)\n 6=0110\n 8=1000\n10=1010\n```\nFirst, ```Generate``` a trie by iterating through each number and creating the trie representation of that number in binary format, beginning with the left-most bit.  Repeat for each number in the array, starting from the trie root for each number.  Redundant trie nodes are left "as is" and are simply traversed over.  New trie nodes are created when needed.\n\nExample iterations within the ```Generate``` function:\n\n\n```\nnum=6:\n\n6=0110\n  3210 (bit position)\n\n             -----root-----\n            /\n          _0             <-- bit position 3\n            \\\n            _1           <-- bit position 2\n              \\\n              _1         <-- bit position 1\n               /\n             _0          <-- bit position 0\n\nnum=8:\n\n8=1000\n  3210 (bit position)\n\n             -----root-----\n            /              \\\n          _0               _1    <-- bit position 3\n            \\              /\n            _1           _0      <-- bit position 2\n              \\          /\n              _1       _0        <-- bit position 1\n              /        /\n            _0       _0          <-- bit position 0\n\nnum=10:\n\n10=1010\n   3210 (bit position)\n\n             -----root-----\n            /              \\\n          _0               _1    <-- bit position 3\n            \\              /\n            _1           _0      <-- bit position 2\n              \\          / \\\n              _1       _0  _1    <-- bit position 1\n              /        /   /\n            _0       _0  _0      <-- bit position 0\n```\n\nSecond, this trie is traversed for each number to ```findMaximumXOR``` of each number when each number is maximally xor\'ed against to ALL numbers\' binary representations in the trie.  This is the act of analyzing each number.  Try to make the left-most bit a 1 in order to create the largest xor value possible.  Repeat from left-most bit to the right-most bit.  Each number is analyzed bit-by-bit while at the same time traversing the previously generated trie representation of ALL the numbers in binary format.  Each number\'s bits are analyzed by beginning with the left-most bit and while simultaneously traversing the trie, starting at the root of the trie.  We are checking if the trie at each bit position contains an ```opposite``` value of each bit in the current number under analysis.  If so, then we know that the xor of two opposite bits is equal to 1, so we set current number\'s maximum xor result ```x```\'s bit for this current bit position ```x|=1```.  Each time this loop iterates, the next bit to the right is analyzed, so we shift the current number\'s maximum xor result ```x``` left by one bit position in order to make room for the next bit\'s analysis result ```x <<= 1```.  This bit shift left-by-one also ensures that the bit set in ```x``` corresponds to the proper bit position previously analyzed.  Once this loop is completed, ```x``` contains the maximum xor value for the current number under analysis compared to ALL other numbers.  Check if ```x``` is larger than any previously calculated maximum xors, and update ```maxXOR``` for each new max xor.\n\nThird, if this is still hard to understand, I\'ve added a commented chunk of this code at the very end of this post.  Without further ado, here is the solution:\n\n```\n#define MAX_BIT_POS 31\n\nclass Solution{\npublic:\n    int findMaximumXOR(vector<int>& nums){\n        auto trie=make_shared<TrieNode>();\n        return trie->findMaximumXOR(nums);\n    }\n    \nprivate:\n    class TrieNode{\n    public:\n        TrieNode() : _1{nullptr}, _0{nullptr} {}\n        \n        int findMaximumXOR(const vector<int>& nums){\n            int maxXOR=0;\n            auto root=Generate(nums);\n            for (auto& num : nums){\n                int x=0;\n                auto curr=root;\n                for (int i=MAX_BIT_POS; i>=0; --i){\n                    x <<= 1;\n                    bool opposite = !(num & (1<<i));\n                    if (opposite){\n                        if (curr->_1){ x|=1; curr=curr->_1; }\n                        else {               curr=curr->_0; }\n                    } else {\n                        if (curr->_0){ x|=1; curr=curr->_0; }\n                        else {               curr=curr->_1; }\n                    }\n                }\n                maxXOR=max(maxXOR,x);\n            }\n            return maxXOR;\n        }\n        \n    private:\n        shared_ptr<TrieNode> _1;\n        shared_ptr<TrieNode> _0;\n        \n        shared_ptr<TrieNode> Generate(const vector<int>& nums){\n            auto root=make_shared<TrieNode>();\n            for (auto& num : nums){\n                auto curr=root;\n                for (int i=MAX_BIT_POS; i>=0; --i){\n                    if (num & (1<<i)){\n                        if (!curr->_1){ curr->_1=make_shared<TrieNode>(); }\n                        curr=curr->_1;\n                    } else {\n                        if (!curr->_0){ curr->_0=make_shared<TrieNode>(); }\n                        curr=curr->_0;\n                    }\n                }\n            }\n            return root;\n        }\n    };\n};\n```\n\nI believe that the hardest to understand piece of of this code is the following.  I\'ve added comments on top of this section of code to help with better understanding:\n\n```\n//\n// find the value of the current number\'s current bit under analysis,\n// and try to find the opposite value in the current trie node\'s children\n//\nbool opposite = !(num & (1<<i));\n\n//\n// opposite is 1\n//\nif (opposite){                            \n\n    //\n    // opposite found in trie, set current number\'s max xor (x\'s) bit\n    // for this bit position and traverse forward to this trie node\n    //\n    if (curr->_1){ x|=1; curr=curr->_1; } \n\n    //\n    // opposite NOT found in trie, traverse the trie to the next trie node.\n    // we know that the next trie node must be pointed towards through _0\n    // since _1 does NOT exist (NOTE: the current number\'s max xor\n    // result for this bit is 0, since an opposite bit value was NOT found.\n    // this can be explicitly coded as x|=0 before iterating forward in the trie\n    // however, the current value of this bit position is already 0.  So this is unnecessary)\n    //\n    else {               curr=curr->_0; } \n\n//\n// opposite is 0\n//\n} else {                                  \n    \n    //\n    // opposite found in trie, set current number\'s max xor (x\'s) bit\n    // for this bit position and traverse forward to this trie node\n    //\n    if (curr->_0){ x|=1; curr=curr->_0; } \n\n    //\n    // opposite NOT found in trie, traverse the trie to the next trie node.\n    // we know that the next trie node must be pointed towards through _1\n    // since _0 does NOT exist (NOTE: the current number\'s max xor\n    // result for this bit is 0, since an opposite bit value was NOT found.\n    // this can be explicitly coded as x|=0 before iterating forward in the trie\n    // however, the current value of this bit position is already 0.  So this is unnecessary)\n    //\n    else {               curr=curr->_1; } \n}\n\n```
[]