✔️Easy All POSSIBLE Solutions | TRIE | MAP | O(N) Efficient
1. APPROACH USING MAP [Accepted] \u2248 1200ms, Slow Compared to 2nd Solution: -\n### EXPLANATION : -\n For a 1 bit number maximum set bits in the binary repres
### **1. APPROACH USING MAP `[Accepted] \u2248 1200ms, Slow Compared to 2nd Solution: -`**\n### **EXPLANATION : -**\n* **`For a 1 bit number maximum set bits in the binary representation of the number will be 1`**\n    **`for a 2 bit number maximum set bits in the binary representation of the number will be 11`**\n    **`for a 3 bit number maximum set bits in the binary representation of the number will be 111`**\n    **`for a 4 bit number maximum set bits in the binary representation of the number will be 1111`**\n   **`and so on \u2026\u2026`**\n\t\n*   **`Now, for a 32 bit number we have 32 bits in memory, so in order to find the largest possible value`**\n    **`of an XOR operation,  the value of XOR should have most of the bits set (i.e. 1)`**\n    **`starting from the left to right.`**\n\n    **`Here, the desired order of set bits is left to right just because we need largest possible value.`**\n    **`For example:`**\n    **`Binary Representation of` 2 is 0010**\n    **`Binary Representation of` 8 is 1000**\n\n    **`So, we can observe that both 2 and 8 have one set bit but the set bit of eight is`**\n    **`more left than set bit of 2 and hence 8 > 2.`**\n\n    **`So the desired order will be left to right.`**\n    **`Now, for getting the maximum number of set bits starting from leftmost bit,`**\n    **`we use mask to keep the prefix of every number of i\u2019th bit.`**\n\n*  **`Now bitwise and of mask and array element will give the prefix of the number.`**\n    **`These prefixes will be stored in a set in order to ignore the repeated values.`**\n\n\t**-> Now we use the important property of XOR:**\n    **`A ^ B = C`**\n    **`A ^ C = B`**\n    **In similar fashion, we can say that**\n    **`prefix ^ set = candidate`**\n    **`prefix ^ candidate = set`**\n    **`Here, we can consider candidate as one of the possible answers.`**\n\t**So, `candidate= ans |(1<<i)` gives the maximum possible output we can get in the i\u2019th iteration.**\n    **`Hence, if xor of any two elements in the set s is equal to ans , we update the ans to candidate.`**\n\n```\n```\n**C++ CODE :-**\n```\nclass Solution {\npublic:\n    int findMaximumXOR(vector<int>& nums) {\n        int N = nums.size();\n        int resMax = 0, mask = 0;\n        set<int> s;\n        for(int i = 31; i >= 0; --i){\n            // create a mask \n            mask = mask | (1 << i);\n            // iterate over the array nums to check the left most digits\n            for(int j = 0; j < N; ++j)\n                s.insert(mask & nums[j]);\n            \n            // now, we have to find the pair which will give us maxXor == (a ^ b)\n            int candidate = resMax | (1 << i);\n            for(auto prefix : s){\n                if(s.count(prefix ^ candidate)){\n                    resMax = candidate;\n                    break;\n                }\n            }\n            // clear the set for the next iteration\n            s.clear();\n        }\n        return resMax;\n    }\n};\n```\n**Time  Complexity : `O(N * log(M)) \u2248 O(N)`, where N : is the size of the array\nSpace Complexity :` O(log(M))`, Where M : is the maximum number present in the array**\n\n```\n```\n### **2. APPROACH USING TRIE `[Accepted] \u2248 250ms, Efficient Solution : -`**\n**Idea : `This question is Same as finding Maximum XOR of Two Numbers in given two Array`**\n\t\t\t   **`And the idea is same as map solution, use bit mask & traverse from back of every digit.`**\n```\nstruct TrieNode{\n    TrieNode *links[2];\n    bool containsKey(int bit){\n        return (links[bit] != NULL);\n    }\n\n    TrieNode *get(int bit){\n        return links[bit];\n    }\n\n    void put(int bit, TrieNode* node){\n        links[bit] = node;\n    }\n};\nclass Trie{\nprivate:\n    TrieNode *root;\npublic:\n    Trie(){\n        root = new TrieNode();\n    }\npublic:\n    void insert(int num){\n        TrieNode* node = root;\n        for(int i = 31; i >= 0; --i){\n            int bit = (num >> i) & 1;\n            if(!node->containsKey(bit)){\n                node->put(bit, new TrieNode());\n            }\n            // if it contains key in trie, move to the next node reference\n            node = node->get(bit);\n        }\n    }\npublic:\n    int getMax(int num){\n        TrieNode *node = root;\n        int maxNum = 0;\n        for(int i = 31; i >= 0; --i){\n            int bit = (num >> i) & 1;\n            // if bit is opposite of the current bit. i.e. (1 - currBit) == 1/0 \n            if(node->containsKey(1 - bit)){\n                // if contains opposite, we can definitely make MaxNum 1 \n                maxNum = maxNum | (1 << i);\n                node = node->get(1 - bit);\n            }else      // if it\'s a same bit as curr\n                node = node->get(bit);\n        }\n        return maxNum;\n    }\n};\nclass Solution {\npublic:\n    int findMaximumXOR(vector<int>& nums) {\n        int N = nums.size();\n        Trie trie;                  // make a trie object\n        for(auto &x : nums) trie.insert(x);\n        \n        // traverse again in the nums for the second num to be xor\n        int res = 0;\n        for(auto &x : nums) res = max(res, trie.getMax(x));\n        return res;\n    }\n};\n```\n**Time  Complexity : `O(N * 32)`, where N : is the size of the array**\n**Space Complexity : `O(N * 32)`**\n\n\nIf you find any mistakes pls, drop a comment\n& If it makes any sense **Please Upvote :)**
['Trie', 'C', 'Bitmask']