Intuitive Python solution


  • 1

    Starting from the 1st bit from left to right, we try to see if we can separate the numbers into 2 groups with bit 1 and bit 0. If they all have bit 0 or bit 0, we ignore that bit. If we can divide them into 2 non empty groups of bit 0 and bit 1, we want to hook one number from group bit 0 with 1 number from group bit 1, right?

    Then what we want to do next for the next bit? We want to divide group bit 0 from previous bit into 2 sub groups: previous bit is 0 and current bit is 0, which I called zz (zero zero), and the group: previous bit is 0 and current bit is 1, which I called zo (zero one). We do the same with the group bit 1 from previous bit, dividing this group into 2 subgroups: previous bit is 1 and current bit is 0, which I called oz (one zero), and previous bit is 1 and current bit is 1, which I called oo (one one).

    Now in order to get the maximum XOR of two numbers, I want to hook zz with oo, and zo with oz, thus creating a new groups of 2: [zz, oo] and [zo, oz]. For each group, we keep doing the same, hook one number from 1 array of the group to another element from the other array of the group.

    The code is followed:

    class Solution(object):
        def findMaximumXOR(self, nums):
            r = 0
            l = [[nums, nums]]
            for i in range(31, -1, -1):
                count = 0
                newL = []
                for pair in l:
                    zz, zo = [], []
                    for zero in pair[0]:
                        if (zero >> i) & 1 == 0:
                            zz.append(zero)
                        else:
                            zo.append(zero)
                    oz, oo = [], []
                    for one in pair[1]:
                        if (one >> i) & 1 == 0:
                            oz.append(one)
                        else:
                            oo.append(one)
                    if len(zz) > 0 and len(oo) > 0:
                        newL.append([zz, oo])
                        count += 1
                    if len(zo) > 0 and len(oz) > 0:
                        newL.append([zo, oz])
                        count += 1
                if count > 0:
                    l = newL
                    r += 1 << i
            return r
    

  • 0
    M

    This was my original thought, but after realizing the complexity of this thought, I didn't proceed since I believe there must be a more elegant solution I didn't know.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.