aboutsummaryrefslogtreecommitdiff
path: root/max_xor_two_num_arr.py
blob: 39a8bc588264e1199169e088d9f896de01556256 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 421. Maximum XOR of Two Numbers in an Array

"""
given an integer array 'nums', return the maximum result of 'nums[i] ^
nums[j]' where '0 <= i <= j < n'
"""


class Solution(object):
    def findMaximumXOR(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans, mask = 0, 0
        for i in range(31, -1, -1):
            mask |= 1 << i
            found = set([n & mask for n in nums])
            start = ans | 1 << i
            for pref in found:
                if start ^ pref in found:
                    ans = start
                    break
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.findMaximumXOR(nums=[3, 10, 5, 25, 2, 8]))
    print(obj.findMaximumXOR(nums=[14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70]))