L6. Maximum XOR of Two Numbers in an Array | C++

No video

L6. Maximum XOR of Two Numbers in an Array | C++ | Java

Рет қаралды 73,226

Күн бұрын

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- Lecture Notes/C++/Java Codes - takeuforward.org/data-structu...
Pre-requisite: Playlist: • L1. Implement TRIE | I...
In this video, we discuss the question Maximum XOR of Two Numbers in an Array.
Please share this channel as much as you can. Also, it's an earnest request to drop a comment "understood" if you are watching this video, so that I get to know you understood from this video.
SDE-Sheet/Linkedin/Telegram/Instagram: linktr.ee/takeUforward
-------------------------------------------------------------------------------------------------------------
Problem Link: bit.ly/3C6IHDp

Пікірлер: 187

@takeUforward 2 жыл бұрын

Lets start a new trend, please comment "understood" and hit a like in case you did :)

@kartikeyasingh5172 2 ай бұрын

We can not have a better explaination than this for this problem.Thank u Striver for providing such a quality content for free.

@rounakmukherjee9540 2 жыл бұрын

Thank you, for all your knowledge, hardwork, awesome teaching..... From your placement series to your Graph, Free ka tree, DP and Trie every playlist is superb!!! I am also from bengal and I always cried bcz I didn't find a teacher who can teach me interview level DSA, but thanks to you and KZfaq... Its really helpful and motivate me a lot when its a person who is also from Kolkata and tier3 student.

@vm1662 12 күн бұрын

Currently preparing for my interviews. Your playlist is a saviour!!!!!! Thank you Striver.

@harshtyagi700 2 жыл бұрын

Understood. One thing I noticed here is that you've declared object of TRIE in stack memory (not using new) and I thought would it make any difference here or not. As we do not need the object of TRIE after the stack of the function( maxXOR() ) is over so we can declare it in stack memory . But in case of struct Node we allocate its memory in heap using new keyword and got a pointer to that memory location. Can we declare that also in stack?

@Noob_Coder1234 7 ай бұрын

fantastic and very smooth explaination of this hard problem just love it and striver op

@shyren_more Жыл бұрын

understood, best explanation, the way you broke down the solution and patched it out together at the end is very impressive!

@sharda16april 4 ай бұрын

Amazing and thank you Striver, as always , for amazing explanation. Understood

@pavanshyamendra6030 2 жыл бұрын

Highly Energetic, Understood

@harishsn4866 2 жыл бұрын

Understood. Thank you for this.

@aarindey 2 жыл бұрын

I think we should have a Node constructor setting links to NULL

@AyushKumar-kh8oh 7 күн бұрын

Understood .... loved your explanation😇

@visase2036 Жыл бұрын

Amazing Explanation. Followup: Retrieve the operands that resulted the maximum xor : Ans: Xor of answer and the input value, resulting in the maximum answer.

@paawansingal788 2 жыл бұрын

very well understood

@priyadarsinipaikaray4998 2 жыл бұрын

awsome explanation

@GurpreetSingh-ez5nr Жыл бұрын

Why are we inserting bits from left to right and why not right to left?

@Yash-uk8ib Жыл бұрын

Brute to find arr[i]^x will be not more than 32*N if i am not wrong?

@harshkanani6605 Жыл бұрын

understood striver sir !!!

@aryanmaniyar7301 8 ай бұрын

Understood Striver, thanks :)

@aryanagrawal4794 2 жыл бұрын

Is there no recursion series before dp?

@evergreen7781 2 жыл бұрын

Legendary explanation bro ❤️

@nishankdeep3084 2 жыл бұрын

understood bhaiya , thank you

@AritraChatterjee 2 жыл бұрын

10:31 looks like he is dubbing for a movie XD Anyways, awesome explanation

@prabudh6713 Жыл бұрын

😂😂😂exactly. That's some energy. Too much that it did the job for a motivational video as well. Good grief, I don't have to go watch one now.

@manikantsharma6108 2 жыл бұрын

understood , Thank u

@engineer8340 Жыл бұрын

Waah Waah Bahut Badhiya Bahut Badhiya

@rajsharma-nk6ot 2 жыл бұрын

great explanation, just the constructor of Trie class should be declared in public scope. Otherwise we will not be able to make the object of the class.

@anandtripathi 2 жыл бұрын

Thank you!

@solosoul3910 9 ай бұрын

you are the best!

@emrulhasan1285 2 жыл бұрын

I am from Bangladesh. Really brother your explanation was awesome. Carry on.

@pulkitaggarwal813 Жыл бұрын

do you even have it jobs there

@utkarsh_108 2 жыл бұрын

understooooood well :)

@aanshi.bansal 2 жыл бұрын

Understood, very nice explanation.

@user-ru9vj6vi5j Жыл бұрын

@striver @takeUforward why not store the numbers in trie starting from the LSB to save space?

@sauravrana1432 10 ай бұрын

then you will not be utilizing the trie . we have used it here so that neglect other number on the way to correct , we are not exploring every branch rather we are moving toward the correct one which will give us maximum xor . It is like Greedy .

@_-6912 2 жыл бұрын

understood Striver.

@DreamLife-05 2 жыл бұрын

Understood sir 👍

@saranghae3720 2 жыл бұрын

understood 🙂

@abhayj8706 2 жыл бұрын

Plz bring DP series 🙏🙏🙏🙏

@PrathameshSaraf Жыл бұрын

shouldn't on line 37 we should or with (1-bit)

@akash_assist 5 ай бұрын

we want to set the bit.... that's why. let's take an example if bit is 1, then (1-bit) is 0 if your entered in the if block that means 0 exist in trie. now what will be xor of 1(original) and 0(opposite) ------> 1 and which means you need to set that bit in answer.....,. or just go & watch the intuition part again 13:58, that will help u for sure....... or just dry run....... u will get it then too..,............. Oh I m 1year late you would've got it by now😂

@rahultiwari7714 2 жыл бұрын

understood sir

@bhushankorg5606 Жыл бұрын

Mind Blowing approach!

@satyampande684 2 жыл бұрын

understood!!

@av21015 Жыл бұрын

To fellow Pythonista class Node(): def __init__(self): self.links=[None for _ in range(2)] def containsKey(self,ind): return self.links[ind]!=None def put(self,ind,node): self.links[ind]=node def get(self,ind): return self.links[ind] class Trie(): def __init__(self): self.root=Node() def insert(self,num): node=self.root for i in num: ind=int(i) if not node.containsKey(ind): node.put(ind,Node()) node=node.get(ind) def findMax(self,num): node=self.root ans=0 for i in range(0,32): ind=int(num[i]) if node.containsKey(ind^1): ans+=(2**(31-i)) node=node.get(ind^1) else: node=node.get(ind) return ans def maxXOR(n, m, arr1, arr2): trie=Trie() for i in arr1: trie.insert('{:032b}'.format(i)) maxi=-1e9 for i in arr2: trie.findMax('{:032b}'.format(i)) maxi=max(maxi,trie.findMax('{:032b}'.format(i))) return maxi

@UECAshutoshKumar 4 ай бұрын

Thank you 🙏

@abhinavrai8430 Жыл бұрын

In summary: For each element in arr2: Try Try Try Trie Awesome videos man I am a fan of your teaching style.

@karanveersingh5535 2 жыл бұрын

Can anyone explain line 37 of c++ code? Couldn't understand. Why (1

@takeUforward 2 жыл бұрын

Watch prereq lecture. L5

@takeUforward 2 жыл бұрын

It sete the ith bit

@DebojyotiMandal 2 жыл бұрын

understood

@mohitsingh7793 2 жыл бұрын

if i use (num&(1i&1) works?

@takeUforward 2 жыл бұрын

Yes

@programmertik2046 2 жыл бұрын

Buddy did u got the answer for the question ?I am also having same doubt

@takeUforward 2 жыл бұрын

I guess due to overflow. May be! Not sure. Should work though

@whysoserious-yj1ku Жыл бұрын

Is it giving segmentation fault? One thing to note. is bit = (num & (1

@anshumaan1024 Жыл бұрын

bhai mera bhi dimaag kharab ho rkha hai isse,

@hannanafridi1649 2 жыл бұрын

Understood Legendary

@kartikrameshchavan6662 Жыл бұрын

Understood 🙏

@ashwathjadhav2859 2 жыл бұрын

sir, please make a playlist on bit manipulation as well

@jitinroy2246 Жыл бұрын

@gudlaudaysai4571 8 ай бұрын

+1@@jitinroy2246

@souravchakraborty9777 2 жыл бұрын

Awesome explanation.

@jaiminsolanki5478 2 жыл бұрын

Understood!

@ajitpalsingh606 29 күн бұрын

when u said like in video ,like button highlighted automatically.

@aayushsingh1512 Ай бұрын

could we not have done this problem in O(32*n) complexity just by going through the bits in reverse form greedily? why is trie even required??

@fearlesscoder2054 2 жыл бұрын

Understood❤

@hemantvardani1436 Жыл бұрын

Thanks

@latchireddiekalavya4683 Жыл бұрын

what is difference in the time complexity of brute force and trie method?

@adityadas5015 Жыл бұрын

brute force would be O(n*m)

@anujbajpai5791 3 күн бұрын

@@adityadas5015 Brute force is simply in for loop we use ^ xor operator so it will be O(n)

@dexterd5397 2 жыл бұрын

Shouldn't it be ^(XOR) instead of | (OR) at line 37 ?

@uvaish6514 2 жыл бұрын

OR is correct as we are directly marking bit as 1 in our answer(maxNum) if opposite bit exists. (Indirectly it is a XOR operation)

@Nikhil-ov6sm Жыл бұрын

wow this is so cool

@smile8510 Жыл бұрын

understood!

@firstyfirst 2 ай бұрын

but why? we can do it in O9N) in signle pass what is the need ?

@yashgupta-fk3zc 2 жыл бұрын

understood..

@girikgarg8 2 жыл бұрын

I couldn't understand why there are 2 arrays in the question

@kousthubhtadanki1237 2 жыл бұрын

@crazyduniya128 2 жыл бұрын

understoooooooooooooooooooood

@yashparmar5722 Жыл бұрын

Thnks❤

@2001chetanshinde Жыл бұрын

Understood😃

@vartika2302 Жыл бұрын

Understood!!

@nikithashekhar1522 Жыл бұрын

Trie constructor should be public not private..right ??

@akash_assist 5 ай бұрын

yes and he mentioned that runnable code is there in description😅😊❤

@saibejjani Жыл бұрын

i will try with trie 😄

@shivammishra2413 16 күн бұрын

understood ......

@priyanshvatsal9791 6 ай бұрын

Understood 😇

@gorakhkumargupta491 9 ай бұрын

best in the world

@arihantjammar8888 9 ай бұрын

Understood 😊

@sanyamwalia217 11 ай бұрын

#understood 😃

@adebisisheriff159 6 ай бұрын

The legend himself

@gargeegupta8725 11 ай бұрын

understood🦋🦋🦋

@tanishkarawat5266 Ай бұрын

Legend

@nischaydhiman7385 2 жыл бұрын

Understood

@Usurperhk 2 жыл бұрын

@shreeshdivyamsinha126 6 ай бұрын

Understood :)

@samirhembrom2559 Жыл бұрын

What is trie?

@addityasharma6426 2 жыл бұрын

understood :-)

@nitishaverma6557 21 күн бұрын

a very similar question to this question was asked in google OA in July 2024 .. regrets i should have watched it earlier :(

@syedmohiuddinh 2 жыл бұрын

Understood 😅

@rohalkurup1350 2 жыл бұрын

US!!!

@yashshah6993 2 жыл бұрын

@pashadyachkov8873 Жыл бұрын

UNDERSTood

@satyamsrivastava9083 2 жыл бұрын

"understood"

@prithvigupta8215 Жыл бұрын

9:36

@sushantkumar4917 2 жыл бұрын

10:32 bro wtf u r shouting😂

@chandrikasaha6301 Жыл бұрын

Was expecting more. What makes you suspect that trie would be beneficial, how you decide what all to store in the trie. this was an easy problem. i was looking for intuitions

@chandrachurmukherjeejucse5816 Жыл бұрын

Did it myself. All thanks to striver.

@harshdasila6680 2 жыл бұрын

undersrtooooooooooddddddddddddddddddddddddddddddddddddddddddddddd

@kshitijmeshram9073 Жыл бұрын

#include struct Node{ Node* link[2]; bool flag; }; int solve(vector arr, int val){ Node* root = new Node; int sz = arr.size(); for(int i=0;ilink[int(s[j])] = new Node; } node = node->link[int(s[j])]; } } struct Node* node = root; string s = bitset(val).to_string(); string ans=""; for(int i=0;ilink[int(s[i])])) ans.push_back(!s[i]); else ans.push_back(s[i]); node = node->link[int(s[i])]; } int cal_val = stoi((ans)); return (cal_val^val); } int maxXOR(int n1, int n2, vector &arr1, vector &arr2) { int maxi = 0; for(int i=0;i

@lakshmanpadigala1605 Жыл бұрын

@FaisalKhan-oy4zz 2 жыл бұрын

Leetcode 421. Maximum XOR of Two Numbers in an Array Gives wrong ans for Test Case: [3, 10, 5, 25, 2, 8] o/p - 17 expected o/p - 28 [14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70] o/p - 119 expected o/p - 127 Please help anyone !!! #tuf #striver code: struct Node{ Node* links[2]={NULL}; bool containsKey(int bit){ return links[bit]!=NULL; } void put(int bit, Node* node){ links[bit] = node; } Node* get(int bit){ return links[bit]; } }; 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); } // return; } int findMax(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 |= (1get(bit); } } return maxNum; } }; class Solution { public: int findMaximumXOR(vector& nums) { int maxi=0, n = nums.size(); // for(int i=0; ifindMax(num)); } return maxi; } };

@shubham320 2 жыл бұрын

In the findMaximumXOR function, in second for loop, the line should be maxi = max(maxi, obj->findMax(num));

@FaisalKhan-oy4zz 2 жыл бұрын

@@shubham320 Thanks buddy

@factsworlda2k547 4 ай бұрын

Raj bhai ye aap please please please kyu krte ho, hum de rahe hai like 💖💖

@nitunsingh6986 2 жыл бұрын

For LeetCode problem here is my solution: struct Node{ Node* link[2]; bool isContain(int bit){ return (link[bit]!=NULL); } void put(int bit,Node* node){ link[bit]= node; } Node* get(int bit){ return link[bit]; } }; class Trie{ 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->isContain(bit)){ node->put(bit,new Node()); } node =node->get(bit); } } int getmax(int num){ Node* node=root; int maxi=0; for(int i=31;i>=0;i--){ int bit=(num>>i)&1; if(node->isContain(1-bit)){ maxi=maxi|(1get(bit); } } return maxi; } }; class Solution { public: int findMaximumXOR(vector& nums) { Trie trie; for(auto &it:nums){ trie.Insert(it); } int ans=0; for(auto &it:nums){ ans=max(ans,trie.getmax(it)); } return ans; } };