best c++ solution without TRIE, solved with bit manipulation with examples, masking explained
\nQuestion : we need to find two elements which have maximum xor.\nApproach : Now in ideal scenarios , what could be the two elements whose xor can produce maxi
```\nQuestion : we need to find two elements which have maximum xor.\nApproach : Now in ideal scenarios , what could be the two elements whose xor can produce maximum result? Its simple (for explanation i am just taking 3 bits): \n\t\t\t\t\t\t\t\t\t\t0   0    0\n\t\t\t\t\t\t\t\t\t\t1   1    1\n\t\t\t\t\t\t\tXOR\t-------------\n\t\t\t\t\t\t\t\t\t\t1   1    1\n\nSo, as of now you realized that maximum possible answer will have all 1\'s or in other terms the \nmaximum possible answer will try to have 1\'s in their extremes left.\n\nNow coming to the next part, we know that for maximum answer you should have all 1\'s. So why\nnot start picking up those answers which have 1 as their leftmost digit. For ex: 100 (i am taking\n3 bits to explain the approach).\nLets suppose we have following elements in the array : [2  3  5]\nBinary representation : [ 0 1 0           0 1 1          1 0 1 ]\nnow what i told you earlier , for maximum possible answer, we need 1 in the leftmost digit . So to get \nthe leftmost digit as 1 , we need 0 at the leftmost position in one number and 1 at the leftmost\nposition in another number. Correct? If no , check this :\n  \n\t\t\t\t0  x  x\n\t\t\t    1  x  x\n\t\t\t   --------\n\t\t\t    1  x  x     and this is what we need right? 1 at left most position !! Great !!\n\t\t\t   \nso which numbers are sharing 0 and 1 at their leftmost position? 2 and 5. So at this moment \nwe know that 2 and 5 will be our answer but in general, you might have more than two\nnumbers satisfying this.\nNow again to get the maximum possible answer, you need 1 at the second position from left. That is\nyou need something like 1   1   x .\nNow to get 1 at the second position , again you need combination of 0 and 1 at second position and \nagain XORing it, will give 1.\nWhat i am saying is --\n                                         x   0   x\n\t\t\t\t\t\t\t\t\t\t x   1   x\n\t\t\t\t\t\t\t\t\t\t --------\n\t\t\t\t\t\t\t\t\t\t 1   1  x    notice the 2nd position\n\t\t\t\t\t\t\t\t\t\t \nIn a similar manner we will proceed for 3rd bit , looking for 0 and 1 at the 3rd position, getting \n1 as a result as a 3rd bit.  So our ans will be 1  1  1.\nIt seems easy right? but i have taken an easy example !!.\nBear with me, we will go slowly , so that anyone can grasp the intution behind the approach.\n\nNow i told you that to get 1 at the first position, we need to look for 1st position in all the numbers\nto pick up a 0 and 1 combo.\n\nNow how to do that? how to pick up the bits from left to right?\nWe will use a MASK. Fancy word but not so fancy.\nWhat is mask? mask is nothing but a combination of few bits which is generally use to check\nwhich position of a binary representation of a number has 1.\nLets take an example :   1   1   0   1 .  Now if we want to check if the left most bit is 1 or not, \ni will AND this number with 1  0  0  0.\n      1  1  0  1\n\t  1  0  0  0\n\t  ---------   performing AND\n\t  1  0  0  0   --> this says that we have 1 at the left most position\nif we want to check if we have 1 at 2nd position, we can do  this:\n  1  1  0  1\n  0  1  0  0\n  ---------\n  0  1  0  0  ---> this says that 1 is present at the 2nd position\n  \nNote: this is one use case of MASK but it just a fancy name, we will use this to pick up the\nprefix of the binary representation of numbers at each step.\nso we will use the same concept in our approach,\nNow we are done with the prequisites, here comes the main logic:\ncreate a variable result=0\nmask=0\nPLEASE MAKE A NOTE I AM USING 3 BITS TO EXPLAIN APPROACH\n1. first we will pick up the prefix of all the binary representation of numbers bit by bit from left to right\n   what i said: \n   if array is [ 2 ( 0  1  0)         3 (0  1  1)       4(1  0  0) ]\n   in 1st iteration we will pick bits till 1st position:\n   **0** 0 0 from 2\n   **0** 0 0 from 3\n   **1** 0 0 from 4\n  in 2nd iteration we will pick bits till 2nd position:\n  **0  1**  0 from 2\n  **0  1** 0 from 3\n  **1  0** 0 from 4\n  in 3rd iteration we will pick bits till 3rd position\n ** 0  1  0** from 2\n ** 0  1  1** from 3\n  **1  0  0** from 4\n  and how do we do this ? by using mask\n  ex: for 2                           010 AND 100->**0**00  1st iteration\n                                      010  AND 110->**01**0     2nd iteration\n\t\t\t\t\t\t\t\t\t  010 AND 111 ->**010**    3rd iteration\n\tmask = mask | 1<<i  <-- this is the mask variable which we will use for ANDing. i means \n\tith position, you will understand it in the code, dont worry.\nnow in each iteration, i will add these prefixes in a set data structure named as prefix_set.\nafter this, we will create a variable lets say temp =result | (1<<i ) and i initially will be 2(why 2 coz\nwe are dealing with 3 bits and i have to shift the 1 towards left to 2th position from right)\n1<<2 means shifting the 1 to 2 places towards left\n\nnow for each element in the prefix_set where we have stored the prefixes, we will pick up that prefix and\nwill XOR with temp and then we will look if the result of this XOR is present in the prefix set or not.\nwhat i said is depicted in the following code:\n\n\t\tfor(int prefix: prefix_set){    //picking up the prefix\n\t\t\tif(prefix_set.count(temp ^ prefix )){     // checking if the XOR exists in the prefix_set\n\t\t\t\tresult=temp;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\nWAIT WHAT ??? why are you XORing now and why are you searching the result of the XOR in the prefix_set?\nThis doesnt make sense !!!!\nBut it will. See,\nlets dry run this thing  we have [2 3 4]\nthe prefix till 1st position [000,000,100] and we are storing this in set.\nprefix_set->[000,100]\nNow temp is result | (1 << i ) , initially result is 0 and i is 2 so\ntemp=0 | (1<<2)\ntemp=100 (4)\nnow what we are doing, we are picking the element from the prefix_set and XORing with temp\n    0 0 0 XOR 1 0 0-->1 0 0   does this result exist in the prefix_set?Yes, then make our result as \n\tof now , equals to temp.\n\t\n\tWhy? temp variable says that i am the maximum possible thing as of now(1 0 0) and if XORing\n\twith the prefix (000) given you something (100) which is already present, then that says\n\tthat we have found one combo of 0 and 1 present in the array. Rings any bell? that combo thing? No?\n\tJust try to dry run on your own and you will get it.\n\t\nlet me just make one more thing clear\na^b=x where x is the maximum possible thing, this is our exact question\nbut in above lines i am doing some thing like a ^ x and trying to look for b in the prefix_set.\nIs this even correct?\nYes, why ? see this->                       x=a^b\n\t\t\t\t\t\t\t\t      \t\ta^x=a^a^b\n\t\t\t\t\t\t\t\t\t\t\ta^x=0^b\n\t\t\t\t\t\t\t\t\t\t\ta^x=b  and similar thing is what we are trying to do\n\t\t\t\t\t\t\t\t\t\t\t\nso we are trying to XOR a with x and we are searching for b and this x is what temp is.\n\nNow its time for some code :\n\nclass Solution {\npublic:\n    int findMaximumXOR(vector<int>& nums) {\n        int result=0;\n        int mask=0;\n        set<int>prefix_set;\n        for(int i =30;i>=0;i--){\n            mask|=1<<i;\n            for(auto num:nums){\n                prefix_set.insert(num&mask);\n            }\n            int temp=result | 1<<i;\n            for(int prefix:prefix_set){\n                if(prefix_set.count(temp^prefix)){\n                    result=temp;\n                    break;\n                \n                }\n            }\n            prefix_set.clear(); // why we are clearing set coz in 1st iteration it will store the \n\t\t\t//prefixes till 1st bit and for storing the prefixes till 2nd bit, we need to clear \n\t\t\t//the previous set content and similarly we will move further\n        }\n        return result;\n    }\n};\n\n\n```\nI know this solution is very lengthy and lots of stuff and concepts are involved. In 1st go, if you are not able\nto understand, i will suggest just dry run the code and you will get it.\nAlso, you might have noticed that at each step, i am storing the prefixes (prefixes till 1st position, prefixes\ntill 2nd position and so on)in a set, we can totally avoid this by using TRIE data structure.\nI will cover this TRIE solution in another post. \n\nThanks a ton for bearing with me till the end . Apologies , if you feel lost somewhere while reading the post.\nJust dry run the code and you will understand the need of finding prefixes and then searching their XOR in \nthe prefix_set again. And yes, using TRIE makes this problem a lot easier !!\n
['Bit Manipulation', 'Bitmask']