clear C++ solution using a Trie (95 percentile)


  • 0
    G
    class Solution {
    public:
    
        #define GET_BIT_VALUE(N,I)\
            (N & (1 << I)) != 0
            
        #define GET_NEG_BIT_VALUE(N,I)\
            (N & (1 << I)) == 0
    
        struct TrieNode
        {
            TrieNode *Nodes[2];
            long long Num;
            
            TrieNode()
            :
            Num(INT_MAX + 1)
            {
                Nodes[0] = Nodes[1] = NULL;
            }
        } *Root;
        
        Solution()
        :
        Root(new TrieNode)
        {
        }
        
        void AddNum(int Number)
        {
            TrieNode *Curr = Root;
            
            for(int i = 31; i >= 0; i--)
            {
                if(Curr->Nodes[GET_BIT_VALUE(Number,i)] == NULL)
                {
                    Curr->Nodes[GET_BIT_VALUE(Number,i)] = new TrieNode;
                }
                
                Curr = Curr->Nodes[GET_BIT_VALUE(Number,i)];
            }
            
            Curr->Num = Number;
        }
    
        int GetBestXor(int Number)
        {
            TrieNode *Curr = Root;
            
            for(int i = 31; i >=0; i--)
            {
                if(Curr->Nodes[GET_NEG_BIT_VALUE(Number,i)])
                {
                    Curr = Curr->Nodes[(Number & (1 << i)) == 0];
                }
                else if(Curr->Nodes[GET_BIT_VALUE(Number,i)])
                {
                    Curr = Curr->Nodes[GET_BIT_VALUE(Number,i)];
                }
                else
                {
                    return (Number);
                }
            }
            
            return (Curr->Num);
        }
    
        int findMaximumXOR(vector<int>& nums) 
        {
            int MaxXor = 0;
            
            for(auto &N : nums)
            {
                int Res = GetBestXor(N);
                AddNum(N);
                MaxXor = max(MaxXor,Res  ^ N);
            }
            
            return MaxXor;
        }
    };

Log in to reply
 

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