<p>Given an integer array <code>nums</code>, return <em>the maximum result of </em><code>nums[i] XOR nums[j]</code>, where <code>0 &lt;= i &lt;= j &lt; n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,10,5,25,2,8]
<strong>Output:</strong> 28
<strong>Explanation:</strong> The maximum result is 5 XOR 25 = 28.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [14,70,53,83,49,91,36,80,92,51,66,70]
<strong>Output:</strong> 127
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
public:
    struct Node
    {
        Node* next[2];

        Node() {
            next[0] = NULL;
            next[1] = NULL;
        }
    };

    struct Node* head;

    void insert(string x)
    {
        struct Node* cur = head;
        for(int i=0;i<x.size();i++)
        {
            if(cur->next[x[i]-'0'] == NULL){
                cur->next[x[i]-'0'] = new Node();
            }

            cur = cur->next[x[i]-'0'];
        }
    }

    string toBinary(int number) {
        if (number == 0) return "0";

        string binary;
        while (number > 0) {
            binary.push_back((number % 2) ? '1' : '0');
            number /= 2;
        }
        return binary;
    }

    int find(string x)
    {
        struct Node* cur = head;
        string ans;
        for(int i=0;i<x.size();i++)
        {
            int ch = x[i]-'0';
            if(cur->next[ch] != NULL)
            {
                //if(x == "11010") cout << 1 << endl;
                ans.push_back('1');
                cur = cur->next[ch];
            }
            else
            {
                //if(x == "11010") cout << 0 << endl;
                ans.push_back('0');
                cur = cur->next[1-ch];
            }
        }

        int lol = 0;
        int b = 1;

        // cout << x << " " << ans << endl;

        //cout << ans << endl;

        reverse(ans.begin(), ans.end());

        for(int i=0;i<ans.size();i++)
        {
            lol+=b*(ans[i]-'0');
            if(i==ans.size() - 1) break;
            b=b*2;
        }

        return lol;
    }

    int findMaximumXOR(vector<int>& x) {
        int n = x.size();

        head = new Node();
        head->next[0] = NULL;
        head->next[1] = NULL;

        vector<string> ans;

        int maxx = 0;

        for(int i=0;i<n;i++)
        {
            string xx = toBinary(x[i]);
            maxx = max(maxx, (int)xx.size());
            ans.push_back(xx);
        }

        for(int i=0;i<n;i++)
        {
            while(ans[i].size() < maxx) ans[i].push_back('0');
            reverse(ans[i].begin(), ans[i].end());

            //cout << ans[i] << endl;

            insert(ans[i]);
        }

        int anss1 = 0;

        //cout << endl;


        for(int i=0;i<n;i++)
        {
            string xx = ans[i];
            for(int j=0;j<xx.size();j++)
            {
                if(ans[i][j] == '1') xx[j] = '0';
                else xx[j] = '1';
            }

            //cout << xx << endl;
            
            anss1 = max(anss1, find(xx));
        }

        return anss1;
    }
};
354171