C++ O(n) using hash table
Based on this solution: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91049/Java-O(n)-solution-using-bit-manipulation-and-HashMap
Based on this solution: https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/discuss/91049/Java-O(n)-solution-using-bit-manipulation-and-HashMap\n\nI think this question looks like the most difficult question until you get to the right track. The idea is you try to find an answer based on possible candidates. I will try to briefly explain it using 8 bits instead of 32 bits. \n\nAssume that we have 8 bit ints. Our max result could be 11111111. To achieve this there must be two numbers when XORed their MSB should give 1.   \n\nSo our first mask is 1000000. (1 shifted all the way to the left). Since we are only checking the first digit we AND the nums with this mask and add to a hash table. Then for each number in our input we test if there\'s a corresponding number that would give this. If there\'s then our next candidate is 11000000, if not then our next candidate is 0100000.\n\nThe trick is that while we are using the hash table we search for " candidate ^ *it " if this exists then it means there is a " nums[x] ^ *it " that gives the candidate based on the XOR property A = B ^ C => A ^ C = B\n\nSo we iterate through all the possible candidates. The outer loop can start from 30 or 31.\n\n\n```\nint findMaximumXOR(vector<int>& nums) {\n    \n        int mask = 0;\n        int result = 0;\n        for (int i=30; i>=0; i--)\n        {\n            mask =  mask | (1 << i);\n            unordered_set<int> myset;\n            for (int i=0; i<nums.size(); i++)\n            {\n                myset.insert(nums[i] & mask);\n            }\n            \n            int candidate = result | (1<<i);\n            for (auto it=myset.begin(); it!=myset.end(); it++)\n            {\n                if (myset.count(candidate ^ *it))\n                {\n                    result = candidate;\n                    break;\n                }\n            }            \n        }\n        \n        return result;\n    \n    }\n```
[]