421. Maximum XOR of Two Numbers in an Array

Link

Solution

class Solution {
    public class Trie{
        Trie[] children;
        public Trie(){
            children = new Trie[2];
        }
        
    }
    
    
    public int findMaximumXOR(int[] nums) {
        Trie root = new Trie();
        int ret = Integer.MIN_VALUE;
        for(int num : nums){
            Trie it = root;
            for(int i = 30; i >= 0; i--){
                int bit = ((1 << i) & num) >> i;
                if(it.children[bit] == null){
                    it.children[bit] = new Trie();
                }
                it = it.children[bit];
            }
        }
        
        for(int num : nums){
            int cur = 0;
            Trie it = root;
            for(int i = 30; i >= 0; i--){
                int bit = ((1 << i) & num) >> i;
                if(it.children[bit^1] != null){
                    it = it.children[bit^1];
                    cur += 1 << i;
                }else{
                    it = it.children[bit];
                }
            }
            ret = Math.max(ret, cur);
        }
        return ret;
        
    }
    
}