Maximum XOR of Two Numbers in an Array | Detailed | Intuition | MICROSOFT | Leetcode-421
Вставка
- Опубліковано 12 вер 2024
- Whatsapp Community Link : www.whatsapp.c...
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
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#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
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.
Thanks a lot. Actually I am planning leetcode contests , one by one more will come.
I posted this video because this will help you to give a try on Last contest’s Qn-4 “Maximum Strong Pair XOR II”
Will soon upload that too.
Thank you very much Sir🙏🏻
@@codestorywithMIK have you uploaded video on that question 4?
Thanks for covering weeklies and bi-weeklies 🙂. I have noticed that over past month, ques r more cp oriented instead of dsa 😅
For anyone who tried after sorting, how r U removing the older values which do not fulfil the condition? Have U defined a new function for removing number-bits?
true.
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& nums, int target, int ans){
unordered_set hash;
for(auto& num: nums){
int setBits = num & target;
int remainingRequired = setBits ^ target;
if(hash.count(remainingRequired)){
// target can be achieved
return target;
}
hash.insert(setBits);
}
return ans;
}
int findMaximumXOR(vector& 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
Very hard work is required to make such content 🙏
🙏🙏❤️❤️
Binge watching all your videos
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
story sunte sunte pta hi nhi chla 56 minutes kab beet gye :)
very nice explanation bhaiya
Thank you so much 😇❤️🙏
Thanku bhaiya ❤ for the explanation ❤
🙏❤️😇
thanks a lot!!!!!!!!!!!!!!!!
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?
Pure Art ❤
please continue this playlist
Bhaiya plz keep on updating your dsa sheet. Thanks 👍
Sure 👍❤️
❤❤❤
Thanks
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;
if(node.child[y]!=null&&node.child[y].minnum){
xor=xor|y
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 left->max > num) {
second += (1 left;
} else {
second += (1 right;
}
} else {
if (temp->right != nullptr && temp->right->min right->max > num) {
second += (1 right;
} else {
second += (1 left;
}
}
}
return second;
}
int maximumStrongPairXor(std::vector& 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
Hi,
Can you please explain the if conditions :
-> (temp->left != nullptr && temp->left->min left->max > num)
-> (temp->right != nullptr && temp->right->min right->max > num)
what is the question number??
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);
if(node->containsKey(1-bit)){
maxNum=maxNum | (1get(bit);
}
return maxNum;
}
};
class Solution {
public:
int maximumStrongPairXor(vector& nums) {
int n=nums.size(), maxXor=0;
sort(begin(nums),end(nums));
for(int i=0;i
16:13 me loop me i++ ji jagha i- aayga
Yes yes.
Thanks a lot 😇🙏❤️