Python O(n) solution easily explained
This problem is tricky so I hope this solution helps!\n\nGeneral form of solution is to find two numbers which have the highest bits complementing each other (0
This problem is tricky so I hope this solution helps!\n\nGeneral form of solution is to find two numbers which have the highest bits complementing each other (0 and 1). Then store that max, look at the next less significant bit and see if another two numbers complement each other (which includes the bits sets from the previous max). If so, this number will\nbe greater than the previous maximum. Steps:\n\n1) Find the new possible maximum by setting the next bit to 1 on the current maximum\n2) use a mask with all 1s up to the current bit i and & all numbers with this mask to see which bit in that number up to bit i are set as 1.\n3) Critical part: to solve this in O(n) it\'s important to know that If a ^ b = c, then  a ^ c = b and c ^ b = a. So, if we are looking for a particular number (in our case a possible maximum) we can do the following search: iterate in the numbers that we &\'d with the mask. If our potental maximum is c, and our current number is a, we\'re looking for another number b that XOR\'d with a gives c. Since we also know from above that a ^ c = b, we can just look for b it directly in our numbers (i.e. b = a ^ c, or in my code, bit ^ possible_mx). \n\n```\nclass Solution:\n    def findMaximumXOR(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        mx,mask=0,0\n        for i in range(31,-1,-1):\n            possible_mx = mx | 1 << i\n            mask = mask | 1 << i\n            bits=set()\n            for num in nums:\n                bits.add(num & mask)\n            for bit in bits:\n                if bit ^ possible_mx in bits:\n                    mx = possible_mx\n                    break\n        return mx\n```
[]