C++ | 2 Solutions | Trie solution | Hashing Solution | Easy | Intuitive | Detailed Explanation |
\nclass Solution {\npublic:\n\t/*\n\t* We have to maximize the bits from left to right. Basically try to make the left ones \'1\'\n\t* Let\'s say we have maximi
```\nclass Solution {\npublic:\n\t/*\n\t* We have to maximize the bits from left to right. Basically try to make the left ones \'1\'\n\t* Let\'s say we have maximized till i-1th bit (31, 30, ... i-1, i, ....0) and say we have got\n\t* a ans = m till now (11011..ith...000000). We can now only check the pairs, which on XOR\n\t* gives us the same as m till i-1th bit. We want the ith bit to be 1, greedy m = 11011...1..000\n\t* It might or might not be possible to get. Let\'s check:\n\t* Add all the nos in a set. Use the fact that if a^b=c ==> a^c=b. So num1^num2 = ans ==> num1^ans = num2\n\t* Think of it similar to (a+b=c) problem. Where you have to find pairs, given c.\n\t* Iterarate on nums and check if there is some number in our set such that it has same starting i bits as ans^numi = k,\n\t* How to do that? Rather than inserting nums in set, insert nums&(11111..till_i_th..00000) in the set. Done!!!!\n\t*/\n\n\tint n;\n\tint findMaximumXOR(vector<int>& nums) {\n\t\tn = nums.size();\n\n\t\tint ans = 0, mask = 0;\n\t\tfor (int i = 31; i >= 0; --i) {\n\t\t\tmask = mask | (1 << i);\n\t\t\tint greedyAns = (ans | (1 << i));\n\t\t\t//Check if possible\n\t\t\tunordered_set<int> s;\n\t\t\tfor (auto &num : nums) {\n\t\t\t\t//We basically insert with first i bits conserved and the rest of the bits are 0 after i\n\t\t\t\ts.insert(num & mask);\n\t\t\t}\n\n\t\t\tfor (auto &prefix : s) {\n\t\t\t\tif (s.find(greedyAns ^ prefix) != s.end()) {\n\t\t\t\t\tans = greedyAns;\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\n\t\treturn ans;\n\t}\n};\n```\nBelow is the standard solution using trie\n```\n#define trav(a, x) for(auto& a : x)\nclass trie {\npublic:\n\ttrie* left;\n\ttrie* right;\n\tint val;\n\n\ttrie(int val) {\n\t\tthis->left = NULL;\n\t\tthis->right = NULL;\n\t\tthis->val = val;\n\t}\n\n\tvoid add(int num) {\n\t\ttrie* temp = this;\n\t\tfor (int i = 31; i >= 0; --i) {\n\t\t\tint bit = ((1 << i) & num) != 0;\n\t\t\tif (bit) {\n\t\t\t\tif (temp->right) {\n\t\t\t\t\ttemp = temp->right;\n\t\t\t\t} else {\n\t\t\t\t\ttemp->right = new trie(1);\n\t\t\t\t\ttemp = temp->right;\n\t\t\t\t}\n\t\t\t} else {\n\t\t\t\tif (temp->left) {\n\t\t\t\t\ttemp = temp->left;\n\t\t\t\t} else {\n\t\t\t\t\ttemp->left = new trie(0);\n\t\t\t\t\ttemp = temp->left;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\treturn;\n\t}\n\n};\n\nclass Solution {\npublic:\n\tSolution() {\n\t\tios::sync_with_stdio(false);\n\t\tcin.tie(NULL);\n\t\tcout.tie(NULL);\n\t}\n\n\tint findMaximumXOR(vector<int>& nums) {\n\t\tauto temp = new trie(2);\n\t\tint n = nums.size();\n\n\t\ttrav(elem, nums) {\n\t\t\ttemp->add(elem);\n\t\t}\n\n\t\tint ans = 0;\n\t\ttrav(elem, nums) {\n\t\t\tauto mover = temp;\n\t\t\tint maxXorFor = 0;\n\n\t\t\tfor (int i = 31; i >= 0; --i) {\n\t\t\t\tint bit = ((1 << i) & elem) != 0;\n\t\t\t\tint bitToAdd = 0;\n\t\t\t\tif (bit) {\n\t\t\t\t\t//Look for 0\n\t\t\t\t\tbitToAdd = (mover->left != NULL);\n\t\t\t\t\tif (bitToAdd) mover = mover->left;\n\t\t\t\t\telse mover = mover->right;\n\t\t\t\t} else {\n\t\t\t\t\t//Look for 1 as 0^1=1\n\t\t\t\t\tbitToAdd = (mover->right != NULL);\n\t\t\t\t\tif (bitToAdd) mover = mover->right;\n\t\t\t\t\telse mover = mover->left;\n\t\t\t\t}\n\t\t\t\tmaxXorFor = ((bitToAdd << i) | (maxXorFor));\n\t\t\t}\n\t\t\tans = max(maxXorFor, ans);\n\t\t}\n\t\treturn ans;\n\t}\n};\n```
[]