[Python] O(32n) solution, explained
Let us try to build the biggest XOR number binary digit by digit. So, the first question we are going to ask, is there two numbers, such that its XOR starts wit
Let us try to build the biggest XOR number binary digit by digit. So, the first question we are going to ask, is there two numbers, such that its XOR starts with `1......` (length is `32` bits). Howe we can find it? Let us use the idea of Problem 1: TwoSum: put all prefixes of lengh one to set and then try to find two numbers in this set such that their XOR starts with `1` (at first we have at most `2` elements in our set). Imagine that there are two numbers, which XOR starts with `1......`, then the next question is there are two numbers with XOR starts with `11.....`, we again iterate through all numbers and find two of them with `XOR` starts with `11`. It can happen that on the next step we did not find `XOR` starts with `111.....`, then we do not change our `ans` and on next step we are looking for `XOR` starts with `1101...` and so on. So:\n\n1. We iterate, starting from the first digit in binary representation of number and go to the right.\n2. For each traversed digit we update our binary mask: in the beginning it is `10000...000`, then it is `11000...000`, `11100...000` and in the end `11111...111`. We need this mask to quickly extract information about first several digits of our number.\n3. Create set of all possible starts of numbers, using `num & mask`: on the first iterations it will be first digit, on the next one first two digits and so on.\n4. Apply TwoSum problem: if we found two numbers with `XOR` starting with `start`, then we are happy: we update our `ans` and break for inner loop: so we continue to look at the next digit.\n\n**Complexity**: Time complexity is `O(32n)`, because we traverse our numbers exactly `32` times. I do not like when this is called `O(n)` complexity, because we have quite big constant here. Space complexity is `O(n)`.\n\n\n```\nclass Solution:\n    def findMaximumXOR(self, nums):\n        ans, mask = 0, 0\n        for i in range(31, -1, -1):\n            mask |= 1<<i\n            found = set([num & mask for num in nums])\n                \n            start = ans | 1<<i\n            for pref in found:\n                if start^pref in found:\n                    ans = start\n                    break\n         \n        return ans\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]