Python (75% speed, 98% memory) - No Trie - Simple, Explained - O(n)
For this explanation, assume: nums = [3, 10, 5, 25, 2, 8]\nAssume that a and b are the numbers with the maximum XOR.\n\nNote: \n1. 2^n > 2^(n-1) + 2^(n-2) + ...
For this explanation, assume: `nums = [3, 10, 5, 25, 2, 8]`\nAssume that `a` and `b` are the numbers with the maximum XOR.\n\nNote: \n1. `2^n > 2^(n-1) + 2^(n-2) + ... + 2^0`. So, in the XOR sum, our first priority will be to get the highest bit possible. \n2. The lowest bit (LSB) is considered the 0th bit. The next bit is the 1st bit and so on. Eg: The highest bit (MSB) in 25 is the 4th bit.\n\n### Steps:\n1. Get the maximum number in `nums`. Here it is 25.\n2. Get the highest bit position possible. In this case, the highest bit is 4th bit.` (25 = 16 + 8 + 0 + 0 + 1)`\n3. Divide `nums` into two groups: First group contains numbers whose 4th bit is 1 (`group1`). Second group contains numbers whose 4th bit is 0 `(group0)`.\n4. So, `a` will be a member of `group1` and `b` will be a member of `group0`\n5. We move to the next bit, i.e., bit 3.\n6. `group0` can be further divided into two groups. First group (`group00`) contains numbers whose 3rd bit is 0. Second group (`group01`) contains numbers whose 3rd bit is 1.\n7. Similarly, `group1` can be divided into `group10` and `group11`\n8. Now, we have multiple cases:\n\t1. **All 4 groups are non-empty.** So the solution will be from `group00` and `group11` or `group01 and group10`. This is because in both these pairs the highest two bits are complementary. This will help us get he maximum XOR.\n\t2. **One of the groups is empty.** Lets assume that the `group01` is empty. This means that the solution must come from the pair: `group00` and `group11` because this pair can provide 1 to the first two bits of the solution. _In general, if one of the pairs exists, then the solution must come from that pair. You can verify this by analysing each case where one of the 4 groups is empty. The final aim is ensure that the first two bits are 11._\n\t3. **Two groups are empty. `group00` and `group10` exist.** The solution will be from this pair.\n\t4. **Two groups are empty. `group11` and `group01` exist.** The solution will be from this pair.\n\t5. **Two groups are empty. `group00` and `group01` exist.** This case can only happen if `group1` is empty. However, if you look at the main `if..else..` clause in the `helper` function, you will notice that if either of the two groups, `group0` or `group1`, is empty, then the `helper` function is called recursively with the non-empty group divided into two groups. So this case need not be handled. _Similar argument will hold when `group11` and `group10` exist._\n\t6. **Only one group is non-empty.** The non-empty group is passed on to the `helper` function recursively.\n\nFurther note: The argument `div_bit` in the `helper` function determines the bit position to compare to divide the groups provided in the function. Each successive recursive call decreases `div_bit` by 1, starting with `max_bit`.\n\nGet an even better explanation here: https://stackoverflow.com/a/9320467/6212985\nEven better, visualise code execution here: http://pythontutor.com/visualize.html#mode=display\n\n### How to determine if a particular bit is 1?\n\nSay you want to determine if the 4th bit 25 is 1. Binary of 25 is `11001`. So, `11001 AND 10000` will change all the bits of 25 to zero except the 4th bit. The 4th bit will retain its original value. This is called **masking**.\n\nIf the result of the AND operation is 0, then the 4th bit is 0. Else, the 4th bit is 1.\n\n### Code\n\n```python\nclass Solution:\n    def findMaximumXOR(self, nums: List[int]) -> int:\n        def helper(group0=[], group1=[], div_bit=0):\n            if len(group0) + len(group1) <= 1: return 0\n            if len(group0) == 1 and len(group1) == 1: return group0[0] ^ group1[0]\n            if div_bit == -1 and group0 and group1: return group0[0] ^ group1[0]\n            if div_bit == -1: return 0\n            nbit = div_bit - 1\n            \n            if group0 and group1:\n                group00, group01 = divide_by_bit(group0, div_bit)\n                group10, group11 = divide_by_bit(group1, div_bit)\n                if (group00 and group11) and (group01 and group10):\n                    return max(helper(group00, group11, nbit), helper(group10, group01, nbit))\n                elif group00 and group11:\n                    return helper(group00, group11, nbit)\n                elif group01 and group10:\n                    return helper(group10, group01, nbit)\n                else:\n                    return helper(group00 or group01, group10 or group11, nbit)\n            else:\n                group0, group1 = divide_by_bit(group0 or group1, div_bit)\n                return helper(group0, group1, nbit)\n                \n        max_num = max(nums)\n        max_bit = int(math.log(max_num, 2)) if max_num else 0\n        return helper(nums, [], max_bit)\n        \n\ndef divide_by_bit(nums, bit):\n    mask = 1 << bit\n    g0, g1 = [], []\n    for num in nums:\n        if num & mask == 0:\n            g0.append(num)\n        else:\n            g1.append(num)\n    return g0, g1\n```\n\n\nP.S: Comment if you can think of some improvements!
['Recursion', 'Bitmask', 'Python3']