<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>

    struct Node{
        Node* link[2];

        bool refExist(char ch){
            return link[ch-'0']!=nullptr;
        }

        void putNode(char ch){
            link[ch-'0'] = new Node();
        }

        Node* getNode(char ch){
            return link[ch-'0'];
        }
    };


    class Trie{
        Node* root;

        public:
        Trie(){
            root = new Node();
        }

            string intToBinString(int num){
                bitset<32> bs(num);
                string bin = bs.to_string();
                return bin;
            }
        int binStringtoInt(string bin){
            // return stoi(bin, nullptr, 2);
            // OR 
            bitset<32> bs(bin);
            int num = bs.to_ulong();
            return num; 

        }

        char findCompliment(char ch){
            return (!(ch-'0')) + '0';
            //OR
            // return ((ch-'0')^1) + '0';
        }

        void insertNum(int num){
            string bin = intToBinString(num);
            Node* cur=root;
            for(auto &chNum: bin){
                if(!cur->refExist(chNum))
                    cur->putNode(chNum);
                
                cur = cur->getNode(chNum);
            }
        }

        //return other num present in the trie such that num^otherNum will be max
        int getOtherNum(int num){
            string bin=intToBinString(num);
            Node *cur=root; 
            string otherNum="";
            for(auto &chNum: bin){
                char compli = findCompliment(chNum);
                if(cur->refExist(compli)){
                    otherNum.append(1, compli);
                    cur = cur->getNode(compli);
                }
                else{
                    otherNum.append(1, chNum);
                    cur = cur->getNode(chNum);
                }
            }

            int ans = binStringtoInt(otherNum);
            return ans;
        }
    };

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie *t= new Trie();
        //insert all nums into trie in the form of binary string
        for(auto &num: nums)                
            t->insertNum(num);

        int maxXor=0;
        for(auto &num: nums){
            int num2 = t->getOtherNum(num);
            maxXor = max(maxXor, num^num2);
        }
        return maxXor;
    }
};
388873