Bht bdhya smjh aaya itni der se bit manipulation smjhna chah rhi thi lekin smjh nhi aa rha tha aapne kraya ekdum smjh aagya.... bhaiya aap sirf prblm nhi solve karte aap sochna sikhate ho ki problem ko approach kese krna h
Sir you are great. I was so worried about coding and tricks. I searched a lot in youtube and all......but all was in vain no one can satisfy me. But your way of explain gave me confidence. Thank you so much for this series. Please don't freez it🙏🙏 You are doing a great job.👍👍
Bhaiya 😂 I can't stop my laugh after watching this video. U covered 3 problems in 1 video 1shot 3 birds. For single number 1 2 3 many RUclipsr doing 3 long videos. You are really legend explained in easy way❤
I solved the 2nd question using another method but yes it took O(n) space complexity. I iterated through the entire array and did the following : 1. If arr[i] ^ arr[i + 1] != 0 means the elements are not same and hence I pushed arr[i] in a vector and did i++ 2. Else I did i = i + 2. 3. Wrote a condition for an edge case wherein the non repeated character might be in the last position. 4. The code checked all the test cases. 5. Time complexity : O(n), space complexity O(n).
@@rishisrivastava9491 bro but question ke array main 2 elements repeat nhi ho rhe par tumhare array main 3 element repeat nhi ho rhe to answer alag aayega hi
I have used the condition int bit = (ans&-ans) and intialise two sum1 and sum2 to 0 and check the condition if it is greater than zero to sum1 ka xor krdo ans ke saath and else sum2 ka xor krdo
Bhaiya can you pls make a video on how to keep ourselves updated on When to apply for girls only competitions, How to know when to apply for a particular competition going on for job/internship hiring??? Pls it would be very helpful for girls with not so much exposure in colleges, who are solely depended on these yt lectures. Pls do the needful 😊😊😊 BTW your videos are very helpful and inspirational.
1 genuine request Bhaiya, code kaise likhna hai iska bhi thoda rough idea de diya karo... Mujhe ye last wale question ka concept to samjh aa gya but mai wo bits wagerh kaise find karunga fir use traverse kaise karunga koi idea nahi hai
I am so glad that i found ur DSA playlist . its Amazing . in 3th question for counting bits we need nested for loop then how its time complexity is 0(n) .
Honestly, this is great. I am curious to try with numbers where the rightmost set bit value is not at 0'th index i.e. 1 is not at 0 for the value of res.
@@lsdxsaurabh2798 Correction in theory is always take resultant XOR's highest bit position means for your case XOR of result (5,7) is (0010), So highest position of Set (1) is 2. Now find all digits having 2nd position is 1, So in array 1 at 2nd position is of (2,2,7). Now XOR of it with result a=(2,2,7 XOR 5,7)=5 and again b= a XOR (5,7)=7. You can test one more case like this [8,8,9,2,9,16,6,2], you can try my understanding on it.
For the k-repetition question, if k = 2n, then you can just go with the same solution as first problem, for 2n+1 however, you'll have to use the counter trick.
I have a doubt in Q2 will the given logic work for [1,1,3,2,4,3]? Bcoz temp=2^4 then temp^(1,1,3,3)=2^4 and temp^(2,4)=0 so we r getting a=2^4=6 and b=0 which are wrong results as it should be 2 and 4??
@@shreyaskarverma8662 no,its right bcz ,here we have seen the case when one number is odd and other is even in temp,but what if both number in temp are even or both are odd ,then temp after solving ex,3^7(both odd) will be 11^111=100,and 2^4=10^100=110,both case last binary digit is zero,so how we will separte this two numbers then?
This approach for q2 is in fact incorrect. The tweak is to find the ith bit which is equal to 1 in the XOR result. In the above example that happened to be the one's bit. This will work because where you find a 1, one of the two numbers will have had zero and the other a one (else xor will not be one). then follow the approach suggested
@@shreyaskarverma8662 Lol it wont work if both distinct element are even or both are odd because last bit of there's XOR will 0 ..... it's men you can't divide array between two part's because last bit of there's xor operation is 0 mean both element's last bit must be 0 or 1 ........ If you try to divide array in two part on the basis of odd , even i.e last bit 0 or 1 still you will got wrong answer ,,,,,,,,,,,,,,,,,,
Correction in theory is always take resultant XOR's highest bit position from right means in your case XOR of result (2,4) is (0110), So highest position of Set (1) is 3. Now find all digits having 3rd position is 1. So in array, 1 at 3rd position is of (4) only and other array (1,1,3,2,3). Now XOR of it with result a=(4 XOR 2,4)=2 and again b= a XOR (2,4)=4. You can test one more case like this [8,8,9,2,9,16,6,2], you can try my understanding on it.
alternate method for 3rd ques: res=xor with all elements of array then res=res^res^res this will get res=(all repeating elements 6 times while non repeating 3 times hence res is the non repeating no)
For every array which contains digits either multiple even [ 1,1,2,2,6,4] or multiple odd [1,1,3,5,2,2 ], the solution will fali, as the in the first case the temp = 6^4 and it will fall in bucket 0 and the result will be 2^2^6^4^4 = 0. In that case, simple solution in python would be temp = [] for element in array: if element not in temp: temp.append(element) else: temp.remove(i) ret temp
Let's say the two odd numbers are 5 and 7. So the final XOR value will be 101 ^ 111 => 010. So in this value the 1 is at the second last place right ? Now accordingly you will have to make subsets based on the second last position values. But now my question is how can we know the position of 1 without completing the entire XOR operation. Then the time complexity will not remain O(n) and it will not be efficient to use XOR and instead a simple nested loop should suffice.
@@akhileshhalkarni8192 set_bit_no = n & ~(n-1); using this formula, where n is the number which you got at last traversing through the array and did ^ with res var.
I can't able to solve all the questions on bits manipulation I tried a lot I understand every concept that u have taught in this video but I failed in building a logic whenever I switch to another question . On gfg every question is looking similar to each other but when I go through them it seems like they are so different to each other. Can you help me out ?? Please.
it's not possible to spoon feed you every concept right? The best way to develop your skills would be to actually try doing a problem and if you don't get the concept see the editorial or even go to the discuss section. Most of the time it will be the solution to your doubt but even if that quench you then youtube that question and see the solution. In this way you will be learning a new concept.
Q2: #include using namespace std; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector nums(n); cin >> nums; int res = 0; int a,b,temp; for(int i = 0; i < n; i++){ temp = res = res ^ nums[i]; } for(int i = 0; i < n; i++){ a = temp ^ nums[i]; } b = a ^ res; cout
in 2nd qns your logic is ok ...but sir if both res value wille XOR of both odd numbers then how?? for eg: 1 2 1 3 2 5 you have taken then res=3^5 both are odd if you devide the array in two parts and did again the xor operation then it will be give (0,6) or (6,0) instead of (3,5) then how??
8 = 1000, 2 = 10, Make group based on second bit from right. so 5 - 101, 4 - 100, 8 - 1000 will be in one group, 3 - 11, 2 - 10, 6 - 110 will be in another group. Consider the first set bit from right in the XOR result.
@@sanjibdas8721 that doesn't make any sense though. So we have to sort of find which bit is different, starting from left , then group based on that. Not sure how that plays out when the bits start appearing the same.
anuj bhaaai in 2nd question ,pehle aapne sbko XOR kra fir jo last mein bchaa usko XOR kra even odd ,alag alag krke, but hm isko seedha bhi toh kr skte hain na even alag odd alag alag alag XOR kro aur alag alag values ayengi.. am i right na?
I am confused about the space complexity part of Q2 as we are creating two buckets(two lists in pythonic code), they got to consume more memory. Hence i feel approaching this question with hashmap approach will yeild similar kind of performance w.r.t. time & space.
Hi, i have a doubt in second question, what if both non repeating elements land up in same bucket , either both odd or both even? How we will modify the approach if need be?
it is not possible that both repeating elements land up in same bucket because two element only occur when they are different and different numbers XOR always 1 so they must have last digit diffrent so they always come in different bucket
In Question 2-> what if all the elements given in array are even numbers. Can we separate elements as odd and even? Will the process fail to get the unique numbers? eg: try question 2 on arr={2,2,4,6,8,4} where all the elements are repeating twice but two non repeating elements 6 and 8
couldn't understand anything in 2021, had spent 2yrs in dev and now this lecture straight goes into my brain❤
Bhaiyaa iss se zyada sahi video bit manp. pe poore youtube pe nhi hai
thanx a lot......
Continue this series ! ❤️
Bht bdhya smjh aaya itni der se bit manipulation smjhna chah rhi thi lekin smjh nhi aa rha tha aapne kraya ekdum smjh aagya.... bhaiya aap sirf prblm nhi solve karte aap sochna sikhate ho ki problem ko approach kese krna h
Sir you are great. I was so worried about coding and tricks. I searched a lot in youtube and all......but all was in vain no one can satisfy me.
But your way of explain gave me confidence.
Thank you so much for this series. Please don't freez it🙏🙏
You are doing a great job.👍👍
Tech burner naam rakhne se subscribers nahi badhte buddy 😆😆
Ye You Tube Saara Educarional & Informational videos me Best tha.
Loved it ...
This is the best way to teach a country.
why do you think so?
aap aur jeetu bhaiya ekdum same ho...
i was sesrching for the explanation of 3rd question.....now understand the concept thanks for the effort
Anuj bhai ki samajhya ho yrr ek baar mai pura concept clear kr diya love you bhai❤❤
one of the best video on youtube for bit manipulation ✌✌
Questions are amazing, especially 3rd one. 👍
if you dont mind can you explain me the third question of this video
2nd problem toh kamaal ka hai bhaiyya😎😎kitni thinking power lagti😀
In love with his method of teaching.
Bhaiya 😂 I can't stop my laugh after watching this video. U covered 3 problems in 1 video 1shot 3 birds. For single number 1 2 3 many RUclipsr doing 3 long videos. You are really legend explained in easy way❤
I solved the 2nd question using another method but yes it took O(n) space complexity. I iterated through the entire array and did the following :
1. If arr[i] ^ arr[i + 1] != 0 means the elements are not same and hence I pushed arr[i] in a vector and did i++
2. Else I did i = i + 2.
3. Wrote a condition for an edge case wherein the non repeated character might be in the last position.
4. The code checked all the test cases.
5. Time complexity : O(n), space complexity O(n).
@Subodh Chandra Shil thats what iam about to say. So, time complexity will be nlogn if we sort it .
if you are using space then why not go for map. it'll be O(n) with space n ofc
Solution of 2nd Question:-
void unique_two(int arr[], int n){
int ans=0;
for(int i=0;i
It won't work with temp become ?????0;
ex. 1 , 1 , 2 , 2 , 3 , 3 , 5 , 7.
temp = 5 ^ 7;
temp = 010.
in second for loop temp will be --> 5 ^ 7 ^ 1 ^ 1 ^ 3 ^ 3 ^5 ^ 7 == 0;
so a == 0;
and b == 5 ^ 7 ^ 0 == 5 ^ 7 == 010 == 2;
a == 0 and b == 2 =========WRONG
brother if wle section mein ek break statement aayega
kyuki arr[8] = {2, 4, 6, 7, 4, 5, 6, 2} kre toh o/p glt aarha hai
@@rishisrivastava9491 bro but question ke array main 2 elements repeat nhi ho rhe par tumhare array main 3 element repeat nhi ho rhe to answer alag aayega hi
I have used the condition int bit = (ans&-ans) and intialise two sum1 and sum2 to 0 and check the condition if it is greater than zero to sum1 ka xor krdo ans ke saath and else sum2 ka xor krdo
Your videos make everything super simple.
Make more videos on bit manipulation... Like finding the nearest greater and smaller number with same number of bitset...
Wow what a series reallly helpful..I have just started this series and this is super helpful.the concepts are alse clear..plz continue this series🙏🙏
Hello....hi before a yr u have started DS can I know how where r u
Anuj leap of faith
Thank you bhaiya :)
Aaj pehli baar maine codechef pey 4+ question solve kiye in starters
just cuz I found this video
what if both the numbers are even?
please continue this series .. great work 💥
Bhaiya can you pls make a video on how to keep ourselves updated on When to apply for girls only competitions, How to know when to apply for a particular competition going on for job/internship hiring??? Pls it would be very helpful for girls with not so much exposure in colleges, who are solely depended on these yt lectures. Pls do the needful 😊😊😊
BTW your videos are very helpful and inspirational.
anuj bhaiya : to next video me next topic hoga :)
Thank you so much Anuj for DSA-One series
it's an amazing course in overall RUclips
Kaafi sikhane ko Mila bhaiya 👍👍👍
1 genuine request Bhaiya, code kaise likhna hai iska bhi thoda rough idea de diya karo... Mujhe ye last wale question ka concept to samjh aa gya but mai wo bits wagerh kaise find karunga fir use traverse kaise karunga koi idea nahi hai
I am so glad that i found ur DSA playlist . its Amazing .
in 3th question for counting bits we need nested for loop then how its time complexity is 0(n) .
its 32*O(n) which can be said to O(n) for large value of n
time o(n)*32 nhi hona chahiye??? and this approach will fail for -ve values
Mai phle apna college se pda ye topic mujhe smaj nhi aya Anuj bhaiya ka dekhne ke bad smaj me aa gya 😎
Thank you so much sir!!! Your teaching is the best!
Bhaiya please it's my request post a self written code
as the code pinned in description is way way more complicated
i agree!!!!
Please dont stop this series😍
Bhai apke all videos Ko apni website par upload kar Dunga with RUclips embed kafi logon ki help ho jayegi
Apka course to premium ka BAAP h
Honestly, this is great. I am curious to try with numbers where the rightmost set bit value is not at 0'th index i.e. 1 is not at 0 for the value of res.
did u found the ans?
SAME HERE .........EX 1 , 1 , 2 , 2 , 5 , 7 IT WILL THROW ANSWER 0 AND 2 WHICH IS INNCORRECT
@@lsdxsaurabh2798 Correction in theory is always take resultant XOR's highest bit position means for your case XOR of result (5,7) is (0010), So highest position of Set (1) is 2. Now find all digits having 2nd position is 1, So in array 1 at 2nd position is of (2,2,7). Now XOR of it with result a=(2,2,7 XOR 5,7)=5 and again b= a XOR (5,7)=7.
You can test one more case like this [8,8,9,2,9,16,6,2], you can try my understanding on it.
Amazing approach.🤯🤯
For the k-repetition question, if k = 2n, then you can just go with the same solution as first problem, for 2n+1 however, you'll have to use the counter trick.
2nd question Explanation :-
int exor = 0;
for(int i=0;i 00000100 & nums[i] gives a no. only when there 1 at that index
for(int i=0;i
good explanation for the xor, thanks for the video :)
I have a doubt in Q2 will the given logic work for [1,1,3,2,4,3]? Bcoz temp=2^4 then temp^(1,1,3,3)=2^4 and temp^(2,4)=0 so we r getting a=2^4=6 and b=0 which are wrong results as it should be 2 and 4??
how did you put 2 and 4 in the same bucket,you didnt understand the logic at all perhaps
@@shreyaskarverma8662 no,its right bcz ,here we have seen the case when one number is odd and other is even in temp,but what if both number in temp are even or both are odd ,then temp after solving ex,3^7(both odd) will be 11^111=100,and 2^4=10^100=110,both case last binary digit is zero,so how we will separte this two numbers then?
This approach for q2 is in fact incorrect. The tweak is to find the ith bit which is equal to 1 in the XOR result. In the above example that happened to be the one's bit.
This will work because where you find a 1, one of the two numbers will have had zero and the other a one (else xor will not be one). then follow the approach suggested
@@shreyaskarverma8662 Lol it wont work if both distinct element are even or both are odd because last bit of there's XOR will 0 ..... it's men you can't divide array between two part's because last bit of there's xor operation is 0 mean both element's last bit must be 0 or 1 ........
If you try to divide array in two part on the basis of odd , even i.e last bit 0 or 1 still you will got wrong answer ,,,,,,,,,,,,,,,,,,
Correction in theory is always take resultant XOR's highest bit position from right means in your case XOR of result (2,4) is (0110), So highest position of Set (1) is 3. Now find all digits having 3rd position is 1. So in array, 1 at 3rd position is of (4) only and other array (1,1,3,2,3). Now XOR of it with result a=(4 XOR 2,4)=2 and again b= a XOR (2,4)=4.
You can test one more case like this [8,8,9,2,9,16,6,2], you can try my understanding on it.
For 3 question , what's TC , n *( log max(A[i]) for finding set bits at i th positions ) is it correct ?
Bhaiyya ji DSA ki le liye aap to... good explanation.👌🏻
All confusion clear 👍❤
In 2nd que... What if both numbers are even/odd... What if last bit is 0..how are we going to separate array then?
congratulations Sir for 300k subscribers❤🎈🎈
Very Good
alternate method for 3rd ques: res=xor with all elements of array then res=res^res^res this will get res=(all repeating elements 6 times while non repeating 3 times hence res is the non repeating no)
works fine for small input but when i tested on interview bit it failed
For every array which contains digits either multiple even [ 1,1,2,2,6,4] or multiple odd [1,1,3,5,2,2 ], the solution will fali, as the in the first case the temp = 6^4 and it will fall in bucket 0 and the result will be 2^2^6^4^4 = 0. In that case, simple solution in python would be
temp = []
for element in array:
if element not in temp:
temp.append(element)
else:
temp.remove(i)
ret temp
Bhaiya bs lage raho apke saath hm bhi lage rhenge!!!!!!!
Amazing Questions with Amazing Explanation.
Bhai i am beginner m code nhi kr paa raha in 3 ques ka plz ap mujhe code send kr skte ho kya
Superlike... Thank you so much! Please continue the great work.
I really appreciate your efforts I know its hard to make such a great videos I'll owe you one!!!!
always thank u for this kind of Great help
Really amazing.aaj laga kuch sikha hai🔥🔥🔥
Thanks a lot bhaiya to clear my doubt
Bhaiya series continue kriyega 🧡🤘
Bhai 3rd question gfg ka solution jo discription me h wo O(n^2) h please give solution of O(n). (Java)
kitta confidence se bolte hai ki "kisi bhi level ka question solve kr log" mtlb kuchh bhi
What if in 2nd ques contains a and b values of both odd... Then it placed on thecsame subset...
Then what should we do...?
Let's say the two odd numbers are 5 and 7. So the final XOR value will be 101 ^ 111 => 010. So in this value the 1 is at the second last place right ? Now accordingly you will have to make subsets based on the second last position values. But now my question is how can we know the position of 1 without completing the entire XOR operation. Then the time complexity will not remain O(n) and it will not be efficient to use XOR and instead a simple nested loop should suffice.
@@akhileshhalkarni8192 set_bit_no = n & ~(n-1); using this formula, where n is the number which you got at last traversing through the array and did ^ with res var.
Formulla :
Get the rightmost set bit, right_most_bit = n & ~(n - 1);
@@akhileshhalkarni8192 wHAT IF THE ELEMENTS OF INT ARRAY ARE NOT VISIBLE TO US?. We are not supposed to make subsets manually by looking at each no.
bhaiya just one thing to say;....we love you
do like if you agree
I can't able to solve all the questions on bits manipulation
I tried a lot I understand every concept that u have taught in this video but I failed in building a logic whenever I switch to another question . On gfg every question is looking similar to each other but when I go through them it seems like they are so different to each other. Can you help me out ?? Please.
it's not possible to spoon feed you every concept right? The best way to develop your skills would be to actually try doing a problem and if you don't get the concept see the editorial or even go to the discuss section. Most of the time it will be the solution to your doubt but even if that quench you then youtube that question and see the solution. In this way you will be learning a new concept.
@@shuvbhowmickbestin Bro did you understood Q2 ......it wont work if both distinct element are ever or both are odd ......
Sir String Algorithms Ka Videos Bhi Banao Plzzz
The course is litt🔥🔥
Q2:
#include
using namespace std;
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector nums(n);
cin >> nums;
int res = 0;
int a,b,temp;
for(int i = 0; i < n; i++){
temp = res = res ^ nums[i];
}
for(int i = 0; i < n; i++){
a = temp ^ nums[i];
}
b = a ^ res;
cout
Amazing explanation 👌👍👍👍👍🤩🤩🤩🤩
ANUJ Bhaiyya,
Please yaar, Goldman Sachs Ki Preparation Strategy and Roadmap pe ek video bna dijiye.
For Q2 what if we have 2 unique number of same type i.e either both even or both odd?
Same doubt🥲
nice question
yes ,for two even distinct number and two odd distinct number this method failed
Best series ❤️❤️🔥🔥🔥🔥
Loved this one bhaiya
in 2nd qns your logic is ok ...but sir if both res value wille XOR of both odd numbers then how??
for eg:
1 2 1 3 2 5 you have taken
then res=3^5
both are odd
if you devide the array in two parts and did again the xor operation then it will be give (0,6) or (6,0) instead of (3,5)
then how??
What we will do in case of two non repeating even number (8,2)
Please tell me
8 = 1000, 2 = 10, Make group based on second bit from right. so 5 - 101, 4 - 100, 8 - 1000 will be in one group, 3 - 11, 2 - 10, 6 - 110 will be in another group.
Consider the first set bit from right in the XOR result.
@@sanjibdas8721 thanks 😊
@@sanjibdas8721 that doesn't make any sense though. So we have to sort of find which bit is different, starting from left , then group based on that. Not sure how that plays out when the bits start appearing the same.
@@sanjibdas8721 WHAT IF THE NUMBERS ARE NOT GIVEN OR VISIBLE TO US?
Bhaiya plz continue the series
anuj bhaaai in 2nd question ,pehle aapne sbko XOR kra fir jo last mein bchaa usko XOR kra even odd ,alag alag krke, but hm isko seedha bhi toh kr skte hain na even alag odd alag alag alag XOR kro aur alag alag values ayengi..
am i right na?
For Q2, isn't it better to use a set to add and remove, instead of creating 2 arrays? Just curious are we saving anything with 2 array soln.
I agree dude.
It means there is a lot to learn, thnks u bhaiya
Bhaiya app bhot achha padhta ho
thank you sir for the video.
Nice video bhai
bhaiya 2nd wala fas jayega method agr input dono missing agr odd honge ya dono missing even honge
Keep this course on
Finally !!!❤❤
Great explanation. Thank you 🔥
Thanks bhaiya continue this 💓
Bhaiya..Thodi si frequency bdha do please...Ase bahut jyada time lg jayga complete hote hote.. Request 🙏
bro bhaiya ka kai saal ka content hai..aise hi thodi na ek baari m nikaal denge :)
god level explanation bhaiya
Excellent dsa course 👍
Was waiting for it 😍😍
I am confused about the space complexity part of Q2 as we are creating two buckets(two lists in pythonic code), they got to consume more memory. Hence i feel approaching this question with hashmap approach will yeild similar kind of performance w.r.t. time & space.
Why two list??? we need only one
Best DSA course.
Hi,
i have a doubt in second question,
what if both non repeating elements land up in same bucket , either both odd or both even?
How we will modify the approach if need be?
it is not possible that both repeating elements land up in same bucket because two element only occur when they are different and different numbers XOR always 1 so they must have last digit diffrent so they always come in different bucket
Ya bhi Thik tha Guru.👍
very helpful. thanks.
Geeksforgeeks pe main method ki jagah
public toLower(String S)
Iska kya meaning hai please reply
What if there are 2 odd elements which have 1 as their right most bit as well as 2 even elements.... We can't solve by dividing into 2 parts.
yeah even i am facing the same issue . @anuj bhaiya can you explain here a bit please
Yes bhaiya
yes this is a drawback of this exact method
Formulla :
Get the rightmost set bit, right_most_bit = n & ~(n - 1);
Question kya hai test case kya bana raha hai 😑
bhaiya in sb question ka code bhi likh dete to aur feel aaa jata
Algorithm for 2nd Question doesn't work if you have more than 1 odd or even numbers preset to find in the array like : [1, 3, 2, 2, 4, 4];
Yes, but actually we have to find the position of rightmost SetBit, then we have divide all elements which have '1' at that position or '0'.
In Question 2-> what if all the elements given in array are even numbers. Can we separate elements as odd and even? Will the process fail to get the unique numbers?
eg: try question 2 on arr={2,2,4,6,8,4} where all the elements are repeating twice but two non repeating elements 6 and 8
yes ,for two even distinct number and two odd distinct number this method failed
Awesome!