Java Trie + short explanation


  • 0
    A

    To solve this problem we can use Trie tree. Lets first insert all the numbers from nums array to the trie. Then we can check for each number the maximum possible answer we can get from the Trie tree. We will start traversing from the last bit. If the i-th bit is 1 and in trie exists an edge with 0 bit their xor will be 1. This edge will be the best edge. Because 00100 is always more than 00011. It is important to have highest bit's xor 1.

    public class Solution {
        public int findMaximumXOR(int[] nums) {
            Trie trie = new Trie();
            for (int val : nums) {
                trie.insert(val);
            }
            
            int ans = 0;
            for (int val : nums) {
                ans = Math.max(ans, trie.count(val));
            }
            return ans;
        }
        
        public class Trie {
    
            private TrieNode root;
        
            public Trie() {
                root = new TrieNode();
            }
        
            public void insert(int num) {
                TrieNode cur = root;
                for (int i=31; i>=0; i--) {
                    int val = (num>>i)&1;
                    if (cur.getNode(val)==null) cur.addNode(val);
                    cur = cur.getNode(val);
                }
            }
        
            public int count(int num) {
                TrieNode cur = root;
                int ans = 0;
                for (int i=31; i>=0; i--) {
                    int val = (num>>i)&1;
                    if (cur.getNode(val^1)==null) {
                        cur = cur.getNode(val);
                    } else {
                        cur = cur.getNode(val^1);
                        ans |= (1<<i);
                    }
                }
                return ans;
            }
        
            private class TrieNode {
                private TrieNode childNodes [];
        
                public TrieNode() {
                    childNodes = new TrieNode[2];
                }
        
                public TrieNode getNode(Integer letter) {
                    return childNodes[letter];
                }
                
                public void addNode(Integer letter) {
                    childNodes[letter] = new TrieNode();
                }
            }
        }
    }
    

  • 0
    Z

    @amanchik Hi cool solution! What are time and space complexities of the solution? By the way, here is my solution


  • 0
    A

    @ZhassanB Your solution's explanation gave me a great hint ("Well, it is clear that, in order to, maximize the resultant number, we have to maximize the number of set bits with higher order. In other words, starting from the left most possible bit") before I solved this problem. Time is O(n32). space min( n32, 2^31-1). I got time and memory limit when I used "HashMap" insted of "TrieNode childNodes []" :)


Log in to reply
 

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