Lc421

class Solution:
    def findMaximumXOR(self, A: List[int]) -> int:
        res = 0
        mask = 0
        for i in reversed(range(32)):
            mask = mask | (1<<i)
            sset = set()
            for a in A:
                left_part = a & mask
                sset.add(left_part)
            #res = res << 1 
            maybe = res | (1 << i)  
            
            for y in sset:
                another = maybe^ y  # if a ^b = c ==> a ^ c = b
                if another in sset:
                    res = maybe 
                    break
        return res 

class Trie:
    def __init__(self,v= None):
        self. v = v
        self.children = [None]*2

class Solution:
    """ tc O(N)  sc O(N)
    """
    def findMaximumXOR(self, A: List[int]) -> int:
        res = 0
        trie = Trie()
        #step1 build trie
        for a in A:
            cur = trie
            for i in reversed(range(32)):
                bit = a & (1 << i)
                bit = 0 if bit == 0 else 1
                if cur.children[bit] == None:
                    cur.children[bit] = Trie(bit)
                cur = cur.children[bit]
        
        # step2 bit position iteration from higher to lower 
        ans = 0
        for a in A:
            cur = trie
            cur_max = 0
            for i in reversed(range(32)):
                bit = a&(1<<i)
                bit = 0 if bit == 0 else 1 
                if cur.children[1-bit] != None:
                    cur = cur.children[1-bit]
                    cur_max  += (1 << i) #cur_max = cur_max *2 + 1 
                else:
                    cur =cur.children[bit]
                    #cur_max = cur_max *2
                    
            ans = max(ans,cur_max)
        return ans