Example: Maximum xor - rFronteddu/general_wiki GitHub Wiki

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

class Solution {
    class TrieNode {
        TrieNode[] children;

        public TrieNode() {
            // Since binary, 0 or 1
            children = new TrieNode[2]; 
        }
    }
    
    TrieNode root;
    
    public int findMaximumXOR(int[] nums) {
        root = new TrieNode();
        for (int num : nums) {
            insert(num);
        }
        int maxXOR = Integer.MIN_VALUE;
        
        for (int num : nums) {
            TrieNode curr = root;
            int currXOR = 0;
            for (int i = 31; i >= 0; i--) {
                // Extract the i-th bit
                int bit = (num >> i) & 1; 
                int oppositeBit = bit == 1 ? 0 : 1;
                
                if (curr.children[oppositeBit] != null) {
                    // Set the i-th bit
                    currXOR |= (1 << i); 
                    curr = curr.children[oppositeBit];
                } else {
                    curr = curr.children[bit];
                }
            }
            maxXOR = Math.max(maxXOR, currXOR);
        }
        return maxXOR;
    }
    

    public void insert (int num) {
        TrieNode curr = root;
        for (int i = 31; i >= 0; i--) {
            // Extract the i-th bit
            int bit = (num >> i) & 1; 
            if (curr.children[bit] == null) {
                curr.children[bit] = new TrieNode();
            }
            curr = curr.children[bit];
        }
    }
}