421. Maximum XOR of Two Numbers in an Array

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        # Compute length L of max number in a binary representation
        L = len(bin(max(nums))) - 2
        # zero left-padding to ensure L bits for each number
        nums = [[(x >> i) & 1 for i in range(L)][::-1] for x in nums]
        
        max_xor = 0
        trie = {}
        for num in nums:
            node = trie
            xor_node = trie
            curr_xor = 0
            for bit in num:
                # insert new number in trie
                if not bit in node:
                    node[bit] = {}
                node = node[bit]
                
                # to compute max xor of that new number 
                # with all previously inserted
                toggled_bit = 1 - bit
                if toggled_bit in xor_node:
                    curr_xor = (curr_xor << 1) | 1
                    xor_node = xor_node[toggled_bit]
                else:
                    curr_xor = curr_xor << 1
                    xor_node = xor_node[bit]
                    
            max_xor = max(max_xor, curr_xor)

        return max_xor

class TrieNode {
  TrieNode[] children;
  public TrieNode() {
    children = new TrieNode[2];
  }
}

class Solution {
  public int findMaximumXOR(int[] nums) {
    if (null == nums || 0 == nums.length)
      return 0;
    
    // get the longest binary representation.
    int maxLen = 0;
    for (int x : nums)
      maxLen = Math.max(maxLen, Integer.toBinaryString(x).length());
    
    // construct binary representation for each number.
    String[] strs = new String[nums.length];
    int padding = (1 << maxLen);
    for (int i = 0; i < nums.length; ++i)
      strs[i] = (Integer.toBinaryString(padding | nums[i]).substring(1));
    
    // construct trie first, and then get the max from the trie.
    TrieNode root = new TrieNode();
    for (String x : strs) {
      TrieNode curr = root;
      for (char c : x.toCharArray()) {
        int bit = c - '0';
        if (null == curr.children[bit])
          curr.children[bit] = new TrieNode();
        curr = curr.children[bit];
      }
    }
    
    int result = 0;
    for (String x : strs) {
      TrieNode curr = root;
      int currRes = 0;
      for (char c : x.toCharArray()) {
        int bit = c - '0';
        if (null != curr.children[1 - bit]) {
          currRes = (currRes << 1) | 1;
          curr = curr.children[1 - bit];
        } else {
          currRes <<= 1;
          curr = curr.children[bit];
        }
      }
      
      result = Math.max(result, currRes);
    }
    
    return result;
  }
}

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        length = len(bin(max(nums))) - 2 # 0bxxx
        res = cur = 0
        for i in reversed(range(length)):
            res <<= 1
            cur = res | 1
            prefix = {num >> i for num in nums}
            for p in prefix:
                if cur ^ p in prefix:
                    res = cur
                    break
        return res