C++, O(n) solution, explanation added
\nint findMaximumXOR(vector<int>& nums) {\n        int n = nums.size();\n        \n        if (n == 0 || n == 1)\n            return 0;\n        if (n == 2)\n  
```\nint findMaximumXOR(vector<int>& nums) {\n        int n = nums.size();\n        \n        if (n == 0 || n == 1)\n            return 0;\n        if (n == 2)\n            return nums.at(0) ^ nums.at(1);\n        \n        list<int> set0;\n        list<int> set1;\n        int i;\n        int j;\n        int maxValue;\n        \n        for (i = 30; i >= 0; i--) {\n            for (j = 0; j < n; j++) {\n                if ((nums.at(j) & (1<<i)) == 0)\n                    set0.push_back(nums.at(j));\n                else\n                    set1.push_back(nums.at(j));\n            }\n            \n            if (set0.size() != 0 && set1.size() != 0) {\n                maxValue = pow(2, i);\n                break;\n            }\n            else {\n                set0.clear();\n                set1.clear();\n            }\n        }\n        \n        if (i == -1)\n            return 0;\n        \n        maxValue += getMaxXor(set0, set1, i-1);\n        \n        return maxValue;\n}\n\nint getMaxXor(list<int>& set0, list<int>& set1, int pos) {\n        int maxValue;\n        list<int> set0list0;\n        list<int> set0list1;\n        list<int> set1list0;\n        list<int> set1list1;\n        int i;\n        list<int>::iterator it;\n        \n        if (set0.size() == 0 || set1.size() == 0 || pos < 0)\n            return 0;\n        \n        for (it = set0.begin(); it != set0.end(); it++) {\n            int value = *it;\n            if ((value & (1<<pos)) == 0)\n                set0list0.push_back(value);\n            else\n                set0list1.push_back(value);\n        }\n        \n        for (it = set1.begin(); it != set1.end(); it++) {\n            int value = *it;\n            if ((value & (1<<pos)) == 0)\n                set1list0.push_back(value);\n            else\n                set1list1.push_back(value);\n        }\n        \n        if (set0list0.size() == 0 && set1list0.size() == 0)\n            maxValue = getMaxXor(set0, set1, pos-1);\n        else if (set0list1.size() == 0 && set1list1.size() == 0)\n            maxValue = getMaxXor(set0, set1, pos-1);\n        else {\n            int maxValue1 = getMaxXor(set0list0, set1list1, pos-1);\n            int maxValue2 = getMaxXor(set0list1, set1list0, pos-1);\n            maxValue = pow(2, pos) + (maxValue1 > maxValue2 ? maxValue1 : maxValue2);\n        }\n        \n        return maxValue;\n }\n```\n\nExample input: [42, 5, 69, 22, 23, 8, 1, 17, 30, 75, 99]\n\nThe max XOR value is (30 ^ 99) = 125. Below are the binary represntations of each number.\n\n42 = 0 1 0 1 0 1 0\n\n5  = 0 0 0 0 1 0 1\n\n69 = 1 0 0 0 1 0 1\n\n22 = 0 0 1 0 1 1 0\n\n23 = 0 0 1 0 1 1 1\n\n8  = 0 0 0 1 0 0 0\n\n1  = 0 0 0 0 0 0 1\n\n17 = 0 0 1 0 0 0 1\n\n30 = 0 0 1 1 1 1 0\n\n75 = 1 0 0 1 0 1 1\n\n99 = 1 1 0 0 0 1 1\n\nEach number in the array is >= 0 and < pow(2,31). So, any number in the array can be represented by atmost 31 bits (bits[30:0]).\nThe for loop in findMaximumXOR (lines 17-33) finds the max bit position where some of the numbers have '0' in that bit position and the other numbers have '1' in that bit position.\nThe numbers that have '0' in that bit position go to set0 and the numbers that have '1' in that bit position go to set1. So, for the example above, we have:\nset0 = {42, 5, 22, 23, 8, 1, 17,30}\nset1 = {69, 75, 99}\nBit position = 6.\nThe value obtained by XORing bit 6 between set0 and set1 (forgetting the low order bits) is pow(2, 6) = 64.\n\nNext, findMaximumXOR() calls getMaxXor() passing set0 and set1 to recursively find the max value of the XOR between numbers in set0 and set1 for the remaning low order bits. The max XOR value would then be 64 + (the max value returned by getMaxXor()).\n\nThe first call would be getMaxXor({42, 5, 22, 23, 8, 1, 17,30}, {69, 75, 99}, 5).\nWhat getMaximumXOR() does is for bit position 5, it splits set0 into two sets - the numbers that have '0' in bit position 5 go to set0list0. The numbers that have '1' in bit position 5 goto set0list1. The same is done for set1 i.e. set1 is also split into two sets set1list0 and set1list1. For this specific example, we have:\n\nset0list0 = {5, 22, 23, 8, 1, 17, 30}\nset0list1 = {42}\nset1list0 = {69, 75}\nset1list1 = {99}\n\nSince at bit position 5 we found set0list0 and set1list1, that means XORing bit 5 (forgetting the low order bits) of numbers between set0list0 and set1list1 woul give pow(2, 5) = 32.\nSo, the maximum XOR value between numbers in set0list0 and set1list1 would be 32 + (set0list0, set1list1, 4).\nArguing on the same lines, the maximum XOR value between numbers in set0list1 and set1list0 would be 32 + (set0list1, set1list0, 4).\nNote that we pair the "opposite" resulting sets to get to the max XOR value i.e. (set0list0, set1list1) and (set0list1, set1list0).\n\nFor this specific example the recursive calls would be:\n\ngetMaxXor({5, 22, 23, 8, 1, 17, 30}, {99}, 4);\nset0list0 = {5, 8, 1}\nset0list1 = {22, 23, 17, 30}\nset1list0 = {99}\nset1list1 = {}\n\ngetMaxXor({5, 8, 1}, {}, 3); ==> This call returns 0 as set1 is empty.\n\ngetMaxXor({22, 23, 17, 30}, {99}, 3);\nset0list0 = {22, 23, 17}\nset0list1 = {30}\nset1list0 = {99}\nset1list1 = {}\n\ngetMaxXor({22, 23, 17}, {}, 2); ==> This call returns 0 as set1 is empty.\n\ngetMaxXor({30}, {99}, 2);\nset0list0 = {}\nset0list1 = {30}\nset1list0 = {99}\nset1list1 = {}\n\ngetMaxXor{{30}, {99}, 1};\nset0list0 = {}\nset0list1 = {30}\nset1list0 = {}\nset1list1 = {99}\n\nSince both set0list0 and set1list0 are empty, we simply ignore this bit position and check the next lower bit position. So:\n\ngetMaxXor({30}, {99}, 0);\n\nset0list0 = {30}\nset0list1 = {}\nset1list0 = {}\nset1list1 = {99}\n\ngetMaxXor({30}, {99}, -1) ==>This call would return 0, as bit position is invalid.\n\ngetMaxXor({42}, {69, 75}, 4);\nset0list0 = {42}\nset0list1 = {}\nset1list0 = {69, 75}\nset1list1 = {}\n\ngetMaxXor({42}, {69, 75}, 3);\n\nset0list0 = {}\nset0list1 = {42}\nset1list0 = {69}\nset1list1 = {75}\n\ngetMaxXor({}, {75}, 2); ==> This call returns 0 as set0 is empty\n\ngetMaxXor({42}, {75}, 2)\nset0list0 = {42}\nset0list1 = {}\nset1list0 = {75}\nset1list1 = {}\n\ngetMaxXor({42}, {75}, 1)\nset0list0 = {}\nset0list1 = {42}\nset1list0 = {}\nset1list1 = {75}\n\ngetMaxXor({42}, {75}, 0)\nset0list0 = {42}\nset0list1 = {}\nset1list0 = {}\nset1list1 = {75}\n\ngetMaxXor({42}, {75}, -1)\n\nIn the recursive calls above, the max value is returned by the path:\ngetMaxXor({42, 5, 22, 23, 8, 1, 17,30}, {69, 75, 99}, 5) //maxValue = 32\ngetMaxXor({5, 22, 23, 8, 1, 17, 30}, {99}, 4) //maxValue = 16\ngetMaxXor({22, 23, 17, 30}, {99}, 3) //maxValue = 8\ngetMaxXor({30}, {99}, 2) //maxValue = 4\ngetMaxXor{{30}, {99}, 1} //maxValue = 0\ngetMaxXor({30}, {99}, 0) //maxValue = 1\ngetMaxXor({30}, {99}, -1) //maxValue = 0\n\nSo, the final max XOR value returned = 64 + 32 + 16 + 8 + 4 + 1 = 125.\n\nThe run time is O(n) because we iterate 31 times, once for each bit position (i.e. bits 30 to 0). During each bit position, we check/visit each number at most once. So, the time complexity would be 31xn or O(n).
[]