/**
knakul853
**/
class Trie{
    public:
    Trie* bit[2];
    bool leaf;

    Trie()
    {
        for(int i=0;i<2;i++)bit[i] = NULL;
        leaf = false;
    }
};

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {


        Trie* root  =  new Trie();

        for(int num : nums)
        {
            insert(num, root);
        }

        int res = 0;
        for( int i=0; i<(int)nums.size(); i++ )
        {
            int num = nums[i];
            Trie* node = root;
            int ans = 0;

            for(int j=31; j>=0; j-- )
            {
                int bit = (num >> j) & 1; // we need to extract one bit so can't do things like (1<<i) &num

                if( node->bit[!bit])
                {
                    ans += (1<<j);
                    node = node->bit[!bit];
                }
                else{
                    node = node->bit[bit];
                }
            }

            res = max(res, ans);
        }

        return res;
    }

    void insert(int num, Trie* root)
    {
        Trie* node = root;

        for(int i=31; i>=0;i--)
        {
            int bit = (num >> i)&1;
            if( node->bit[bit] == NULL )
            {
                node->bit[bit] = new Trie();
            }

            node = node->bit[bit];
        }

        node->leaf = true;
    }
};