Fastest 55ms C++ easy to understand code O(n).


  • -2
    J

    '''
    class Solution {
    public:
    struct node{
    node* child[2];
    //bool isleaf;
    };
    node* getNew(){
    node* nn = new node;
    for(int i = 0 ; i<2 ; i++){
    nn->child[i] = NULL;
    }
    //nn->isleaf = 0;
    return nn;
    }
    int vv(int ex , node* root){
    node* nn = root;
    int ans = 0;
    for(int i = 31 ; i>=0 ; i--){
    int val = ((ex&(1<<i)) > 0);
    if(nn->child[1 - val]){
    nn = nn->child[1 - val];
    ans += (1<<i);
    }
    else{
    nn = nn->child[val];
    }

    }
    return ans;
    

    }
    void insert(int ex , node* root){
    node* nn = root;
    for(int i = 31 ; i>=0 ; i--){
    int val = ((ex&(1<<i)) > 0);
    if(nn->child[val] == NULL){
    nn->child[val] = getNew();
    }
    nn = nn->child[val];
    }
    }
    int findMaximumXOR(vector<int>& nums) {
    if(nums.size() == 0)
    return 0;
    node* root = getNew();

        insert(nums[0] , root);
        
        int ans = 0;
        for(int i = 0 ; i<nums.size() ; i++){
        	int num = nums[i];
        	insert(num , root);
        	ans = max(ans , vv(num , root));
        	//cout<"rr"<<endl;
    	}
        return ans;
    }
    

    };

    '''


Log in to reply
 

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