C++| Beginner Friendly | Greedy | Hashsets Solution | Detail Explanation
For approching this problem we have to know xor\'s property.\nxor is 1 when two bits are diffrent\n(0^1 = 1 and 1^0 = 1)\nand we need maximum xor so we will gre
For approching this problem we have to know xor\'s property.\nxor is 1 when two bits are diffrent\n(`0^1 = 1 and 1^0 = 1`)\nand we need maximum xor so we will greedely try to set all MSBs from left in our answer if possible.\n\nprefix variable in our solution will help us to get first i bits from nums\n(prefix will grow like : `10000 -> 11000 -> 11100 -> 11110 -> 11111`)\n\nthen we are storing these prefix bits of nums in a hash set\nn & prefix  will give us first i bits of nums\nfor example if `n = 25 -> 11001 and prefix is 11100 `\nso n & prefix will get us ->` 11000 `( first i bits of this number n which is 110)\n\nnow if we want to set ith bit of answer\nlet say` c = ans | (1<<i)` (this is how we set ith bit of any number)\nthen we have to check if there exits two number whose prefixs till i bits\nwill give us xor value = c\n, `a ^ b = c `\nas we fixed c and when iterating in set we will fix one number `a` then\n`b` will be` a ^ c` , { as `a^b = c` then `a^c = b` }\njust like two sum if we got a, does b exist which give us c\nso we have to check do b exists in our set\nif yes our ans will have this ith bit = 1, thus `ans = c`\nelse answer will remain same as this bit will 0 otherwise\n\n**Below is c++ code :**\n```\n\tint findMaximumXOR(vector<int>& nums) {\n         int ans = 0,prefix = 0;\n         // intially we have all bits 0 in our ans and prefix\n         for(int i=31;i>=0;i--)\n         {\n             prefix = prefix | (1<<i);\n\t\t\t // prefix will have first i MSBs 1\n\t\t\t unordered_set<int> s;\n\t\t\t \n             for(int n : nums) // get prefix of first ith bits\n                 s.insert(n & prefix); // n& prefix will get us first i MSBs of number n\n\t\t\t\t \n             // now lets check can we get this bit  1 in our ans\n             int c = ans | (1<<i);  // we setted ith MSB of our answer and stored it in c\n             // now we have to check can we get this from nums and we stored first ith MSBs of nums in set\n             // we want two nums a and b such that a ^ b = c\n             // just like two sum if we got a, does b exist which give us c\n             // and we know a^b = c then b = a^c so we will check in set does b exits for given a to achive c\n             for(int a : s)\n             {\n                 int b = c^a;\n                 if(s.find(b) != s.end()) // if b exists\n                 {\n                     // our answer will have this bit set\n                     // so answer now\n                     ans = c;\n                     break;\n                 }\n             }\n\t\t\t // if we cant get pairs a and b such a^b = c then this bit will remain unsetted (0)\n         }\n        return ans; // this is max xor we can get by two pair in nums\n    }\n```\n\n\nDry run for first testcase :\n`nums = [3,10,5,25,2,8]`\nin binary : \n```\nnums = [00011 , 01010 , 00101 , 11001 , 00010 , 01000]\n```\n\nour `prefix = 00000 and answer = 00000` intially\n\nfor First MSB, i = 4  : \n\t\tprefix = 10000;\n\t\tfor n ->\n```\n\t\tn = 3 =   00011 so ( n & prefix ) = 00000\n\t\tn = 10 =  01010 so ( n & prefix ) = 00000\n\t\tn = 5 =   00101 so ( n & prefix ) = 00000\n\t\tn = 25 =  11001 so ( n & prefix ) = 10000\n\t\tn = 2 =   00010 so ( n & prefix ) = 00000\n\t\tn = 8 =   01000 so ( n & prefix ) = 00000\n```\n\t\t\n```\n\t\t\t\t//so set\n\t\t\t\t\t\ts = [ 00000 , 00000 , 00000 , 10000 , 00000 , 00000 ]\n\n// ( prefix of  1 MSB of nums : 3        10       5      25    2      8       )\n```\nnow we want this bit of ans to be set\n`so c = 00000 | (10000) = 10000` \nwe have to check can we get c in set by two numbers a and b , a^b = c or for a given a do b exits such that b= a^c\nfor a : s\n`\tb = 00000 ^ 10000 = 10000`\n\tdo b exist in set , yes so our `ans = c = 10000`\n\nnow for second MSB , i = 3 :\nprefix = 11000\n\n```\n\t\t\t\t//so set\n\t\t\t\t\t\ts = [ 00000 , 01000 , 00000 , 11000 , 00000 , 01000 ]\n\n// ( prefix of first 2 MSB of nums : 3        10       5      25    2      8       )\n```\n\ncan we set this bit of answer : \nso` c = 11000`\nso yes for `a = 00000` there exist `b = 11000` which will give `a^b = 11000`\nso `ans = 11000 `now \n\nlike this we will check for all other bits greedly and check can we set it or not in answer\n\n\n**Hope it helps to understand !**\n\n
['Greedy', 'C', 'Ordered Set']