Maximum XOR of Two Numbers in an Array | Detailed | Intuition | MICROSOFT | Leetcode-421

This is the 3rd Video on our Trie Playlist
In this video we will try to solve a very good Trie problem - Maximum XOR of Two Numbers in an Array (Leetcode -421).

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Maximum XOR of Two Numbers in an Array
Company Tags : MICROSOFT

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[alokmishra]

Hello Sir, I am huge fan of your teaching style because it has helped me alot in understanding the approach of the question very well.I have a small request from you to please find out your some valuable time and help in solving leetcode contests also🙏🏻.It will definately be very helpful for many of us.Thank you.

[xiaoshen]

Thanks for covering weeklies and bi-weeklies 🙂. I have noticed that over past month, ques r more cp oriented instead of dsa 😅

[mohammadrizabul]

thank you for your beautiful explaination .

[yadav.nitin]

Very hard work is required to make such content 🙏

[iWontFakeIt]

I solved it using bit manipulation logic, but loved your trie logic.
Below is my bit manipulation based code.

class Solution {
public:
int solve(vector<int>& nums, int target, int ans){
unordered_set<int> hash;
for(auto& num: nums){
int setBits = num & target;
int remainingRequired = setBits ^ target;

// target can be achieved
return target;
}
hash.insert(setBits);
}
return ans;
}
int findMaximumXOR(vector<int>& nums) {
int n = nums.size();
// logic: we have to maximize the xor, so in order to maximize we need more and more
// set bits in th 0 - 31 position, also the set bits should be more towards the msb
// of the resulting number, now we find pairs iterating for every i-th bit and looking for
// if the i-th bit can be set or not. Also, while checking for the next i-th bit, preserve
// the current i-th bit in the number we are looking for
int ans = 0;
for(int i=31; i>=0; i--){
// start from msb since we are needed to maximize
ans = solve(nums, ans | (1<<i), ans);
}
return ans;
}
};

[lofireverbz-wygo]

story sunte sunte pta hi nhi chla 56 minutes kab beet gye :)
very nice explanation bhaiya

[Anubhav__Code]

bhaiya aapne bhut acha samjhaya but ek chiz samajh me nahi aai ki hmko kaise dekh ke pata lagega ki ye trie se hoga??? Mai to isko bit manipulation se solve kr rha tha

[infinitygaming]

sir kya hum esme inverse find ker sakte he number ka binary form ka and then find ker sakte he hash map me agar present he ke nehi kya ye sahi appraoch hee?

[prajwalshaw]

Bhaiya plz keep on updating your dsa sheet. Thanks 👍

[mayankshakya]

16:13 me loop me i++ ji jagha i— aayga

[sauravchandra]

Why am I getting a TLE on this code, I even tried using lowerbound to find the index till which j would go
struct Node{
Node* links[2];

bool containsKey(int bit){
return (links[bit]!=NULL);
}
Node* get(int bit){
return links[bit];
}
void put(int bit, Node* node){
links[bit]=node;
}
};
class Trie{
private: Node* root;
public:

Trie(){
root=new Node();
}
void insert(int num){
Node* node=root;
for(int i=31;i>=0;i--){
int bit=((num>>i)&1);
if(!node->containsKey(bit)) node->put(bit, new Node());
node=node->get(bit);
}

}
int getMax(int num){
Node* node=root;
int maxNum=0;
for(int i=31;i>=0;i--){
int bit=((num>>i)&1);

maxNum=maxNum | (1<<i);
node=node->get(1-bit);
}
else node=node->get(bit);
}
return maxNum;
}

};
class Solution {
public:
int nums) {
int n=nums.size(), maxXor=0;
sort(begin(nums), end(nums));

for(int i=0;i<nums.size();i++){
Trie trie;
for(int j=i;j<nums.size();j++){
if(nums[j]-nums[i]>nums[i]) break;
trie.insert(nums[j]);
}
for(int j=i;j<nums.size();j++){
if(nums[j]-nums[i]>nums[i]) break;
maxXor=max(maxXor, trie.getMax(nums[i]));
}
}

return maxXor;
}
};

[dayashankarlakhotia]

leetcode qn no4
class Solution {
TrieNode root=new TrieNode ();
public maximumStrongPairXor (int[]nums){
int ans=0;
for(int num:nums){
insert(num);
}
for(int num:nums){
int xor=find(num, num*2);
ans=Math.max (ans, num^xor);
}
return ans;
public void insert (int num){
TrieNode node =root;
for(int i=20;i>=0;i--){
int idx=(num>>i)&1;
if(node.child[idx]==null){
node.child[idx]=new TrieNode();
}
node=node.child[idx];
node.min=Math.min (node.min, num);
node.max=Math.max (node.max, num);
}
}
public find(int num, int range){
TrieNode node=root;
int xor=0;
for(int i=20;i>=0;i--){
int x=(num>>i)&1;
int y=1-x;
&&node.child [y].max>num){
xor=xor|y<<i;
node=node.child[y];
}else {
xor=xor|x<<i;
node=node.child[x];
}
}
return xor;
}
}
class TreeNode {
TrieNode[]child =new TrieNode[2];
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
}
this is code of leetcode 4.🎉😂❤

[ankitjha]

Question 4

class Solution {
public:
struct TrieNode {
TrieNode* left;
TrieNode* right;
int min;
int max;

TrieNode () {
left = nullptr;
right = nullptr;
min = INT_MAX;
max = INT_MIN;
}
};

void insert(TrieNode* root, int &num) {
TrieNode* temp = root;

for (int i = 31; i >= 0; --i) {
int i_bit = (num >> i) & 1;

if (i_bit == 1) {
if (temp->right == nullptr) {
temp->right = new TrieNode();
}
temp = temp->right;
} else {
if (temp->left == nullptr) {
temp->left = new TrieNode();
}
temp = temp->left;
}

temp->min = min(temp->min, num);
temp->max = max(temp->max, num);
}
}

int findXOR(TrieNode* root, int &num) {
TrieNode* temp = root;
int second = 0;

for (int i = 31; i >= 0; --i) {
int i_bit = (num >> i) & 1;

if (i_bit == 1) {
if (temp->left != nullptr && temp->left->min <= 2*num && temp->left->max > num) {
second += (1 << i) * 0;
temp = temp->left;
} else {
second += (1 << i) * 1;
temp = temp->right;
}
} else {
if (temp->right != nullptr && temp->right->min <= 2*num && temp->right->max > num) {
second += (1 << i) * 1;
temp = temp->right;
} else {
second += (1 << i) * 0;
temp = temp->left;
}
}
}

return second;
}

int nums) {
TrieNode* root = new TrieNode();
int n = nums.size();

for (int i = 0; i < n; ++i) {
insert(root, nums[i]);
}

int ans = 0;

for (int i = 0; i < n; ++i) {
int secondNumber = findXOR(root, nums[i]);
cout << "Min: " << nums[i] << " Max: " << secondNumber << " XOR: " << (nums[i] ^ secondNumber) << endl;

if (abs(nums[i] - secondNumber) <= min(nums[i], secondNumber)) {
ans = max(ans, nums[i] ^ secondNumber);
}
}

return ans;
}
};