This video is the third and last part of the 3 video series on Bit Manipulation. We’ll be talking about: XOR operations Q1. Find the only non-repeating element in an array where every other element repeats twice. - https://www.geeksforgeeks.org/find-el… Q2. Find the two non-repeating elements in an array where every other element repeats twice. - https://www.geeksforgeeks.org/find-tw… Q3. Find the only non-repeating element in an array where every other element repeats thrice. - https://www.geeksforgeeks.org/find-un…
💸 Visit https://www.educative.io/anuj to avail discount on all courses on Educative! 💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags: #anujbhaiya #dsaone
Ignore these tags:
bit manipulation photo manipulation java bit manipulation bit manipulation in java manipulation tutorials advanced photo manipulation bit manipulations photoshop manipulation bit manipulation interview questions manipulation bit manipulation for competitive programming photoshop manipulation tutorial advance photo manipulation bit manipulation code photo manipulation tutorials photo manipulation photoshop problem solving bit manipulation in hindi bit manipulation in python min xor bit manipulation xor bit manipulation bit manipulation code bit manipulations bitwise manipulation and masks bit manipulation questions bitwise manipulation manipulation bit manipulation basics bit manipulation utf anuj bhaiya bit manipulation xor bitwise xor bit manipulation interview questions xor operation bit masking dsa one non repeating numbers dsa bit manipulation playlist c++ anuj bhaiya dsa xor operator xor problem anuj bhaiya bit manipulation anuj find the two non-repeating elements in an array of repeating elements/ unique numbers 2 java anuj bhaiya bit manipulation anuj bhaiya bit manipulation c++ dsaone bit manipulation java bitwise dijkstra’s algorithm bit manipulation striver dsa course find missing and repeating number in array bit manipulation playlist coding blocks dsa anuj bhaiya xor equation codechef solution anuj bhai bit manipulation anuj bit manupulation xor equal xor in c++ xor properties anuj bhaiya java bit bit manipulation for competitive programming bit manipulation in java bit manipulation playlist java bitmasking bitwise xor operator algorithms anuj kumar sharma bit manipulation in c++ bitwise operators in c++ divide two integers dsa one course how to win friends and influence people audiobook ishan sharma love babbar maximum xor optimal xor set single number leetcode xor equation xor problem codechef advanced c++ anuj sharma apna college array in c++ array in java backtracking anuj bhaiya basic data structures bit manipulation in c bit manipulation pepcoding bit mask bitmask bits manipulation bitwise and of numbers range bitwise and of the array gfg bitwise manipulation bitwise operator bitwise operators in java c++ array coding tricks competitive programming count set bits count total set bits daa data structures data structures and algorithms data structures and algorithms playlist dsa full course dsa in java dsa playlist duplicate element in an array dynamic programming eric clapton even subset xor even xor evenxor find the missing and repeating number first repeating element in an array of integers functions in python get bit greedy algorithms hashmap in java heap how to get deep voice how to pull request github hum barf pe chalte hain implement min stack java interview questions and answers k smallest element in array kafka spring boot log4j2 tutorial in java loose coupling and tight coupling in java love babbar dsa love babbar roadmap max xor of two number maximum subset xor maximum xor of two numbers maximum xor subset minimum number of flips to make the binary string alternating missing and repeating number in array nick white nikhil tokyo non repeating numbers gfg non zero subarray xor permutations and combinations problems and unique numbers programming in java reverse bits leetcode salam e ishq single number 2 leetcode single number iii string manipulation
Content
0 -> What is up guys. Welcome to the DSA 1 course and today we are going to talk about Bit Manipulation.
4.332 -> Today we'll be solving advance level questions. We'll learn about XOR and how powerful it is!
10.641 -> We have already discussed it but we'll explore a little more about it.
15.003 -> Today we'll be solving advance level questions.
17.819 -> After today's video, you can solve any level questions under Bit Manipulation easily.
23.025 -> I'll give you assignments today, try it, you'll be able to solve it easily.
28.43 -> Let's start.
29.147 -> So, basically these are 3 questions. We'll be solving it.
32.815 -> XOR, we already know about it.
34.615 -> If we make the truth table of XOR, it'll look something like this.
38.246 -> If both the Bits are same then answer is 0, if they are different then the answer is 1.
44.174 -> You can also say that when two no. are same then XOR will always be 0. Suppose any number
50.8 -> Suppose 5, then 5^5 =0 (always).
54.709 -> Why? because if you'll change it into bits, still 5 is 101, right!!
58.536 -> and this will be the same as well. If you'll XOR it then it'll be 000
66.303 -> Which means, if you'll XOR a number by itself, it'll always be 0.
69.886 -> This is the1st property.
71.653 -> 2nd property of XOR is that if you XOR any number, suppose n
78.311 -> that will always be equal be n.
80.571 -> Alright! So if you XOR any number with 0, the it'll be the number itself.
84.496 -> So these are some properties which makes XOR useful and then we'll be solving the question.
90.189 -> Question is to find the only non- repeating element in an array where every element repeats twice.
95.606 -> Suppose this is the array and each no is being repeated twice.
99.165 -> Except 3, so you have to tell which is that element?
103.635 -> So the way in which we are understanding is very simple, basically you will apply the loop two times easily.
109.74 -> And, you'll check, for 5 if there is another 5 present or not.
113.513 -> If second 5 is present then you'll move forward, if not then 5 is the answer.
117.928 -> It can be a way but if we solve this the time complexity will be O(n^2).
122.884 -> We can make it better. A better way can be we use space here, Hash map.
128.754 -> where we'll be suing O(n) space, but then we'll not be able to solve O(n), how?
133.804 -> Just as we got 5 we moved it into Hash map, and then in Hash Set.
138.246 -> We included 5 in the set then 4, 1 again when you'll get 4 then, then you have to remove out of it.
148.043 -> We got 3 and included it, same with 5 as well, the we got 1, it's already in set so remove it
154.6 -> so the answer inside the set would be the reaming 3.
157.309 -> It can be this way as well, but we are using the space, either use O(n) space or O(n^2).
164.882 -> Can there be a better way? Yes, there can be one.
168.303 -> In which you can solve this in constant space and you can solve it in O(n) time complexity. Its a very good way.
173.999 -> We'll us ethe property of XOR and let's see how it'll be used upon.
178.172 -> Basically. We'll do XOR of all the numbers, one by one.
182.234 -> We'll run a loop and we'll go on doing XOR.
185.731 -> So, initially, our variable would be 0. If you XOR any no. with 0 it'll be the number itself so there's no harm in starting with 0
192.727 -> So we added 0. Now we'll XOR this result with everyone.
198.8 -> Whenever you XOR 0 with 5, answer will be 5 right!
206.343 -> Now, in the next step XOR it with 4 so now it'll be 5^4.
213.6 -> Something will be the answer, don't take tension about the result here.
218.266 -> Then you XOR this result with 1
221.857 -> Its is 5^4^1. Right! Now when you XOR it with 4 again.
228.424 -> Whenever it gets two elements and XOR them, it becomes 0, right!
231.797 -> two no. that are same, if XOR become 0 and then if you XOR it with 0, it'll be the no. itself.
236.351 -> You cans ay that when you XOR two numbers, they cancel each other
241.319 -> You can say that after doing this the result will be equal to 5^1. Means 4 never exited in this array.
251.992 -> Basically both the 4's will be eliminated.
255.705 -> So now it's 5^1. Now let's take the next number. Now the answer will be 5^1^3.
261.429 -> Right! Now the next no. is 5,we'll XOR it with 5.
266.072 -> Now, 5 is twice so they'll cancel each other.
271.178 -> Now it'll be 1^3.
275.614 -> Now, the next is 1.
279.051 -> After doing XOR, again 1 will be cancelled.
282.77 -> And the result will be 3.
284.684 -> You have used a variable and you have XOR each element through this help and at the end you'll be left with the number
293.118 -> which is your answer. If you want to see the proof, you can see it easily.
297.297 -> Suppose, the array is 5, 6, 5.
303.84 -> I'll XOR of these 3 numbers and let's see what happens. 5 is 101, right!
309 -> 6 is 110. XOR it, it'll be 011.
316.246 -> now it can be anything, for now its 011, it doesn't matter. Now XOR it with 5, which is 101.
324.714 -> The answer is 110 that is your 6.
331.171 -> So you can see that both the 5's are cancelled in a way and the answer is 6.
335.141 -> So we are using this property here and its very amazing, you can solve this question easily in a constant space with its help.
344.342 -> It was an awesome property of XOR. Let's see the second question.
347.219 -> Its this one, where we have to find 2 non- repeating elements. Its a slightly better question than before.
353.452 -> This was a very basic level question. let's see this one because it's good as well.
356.447 -> The Question is that you have been given so many elements and each is being repeated 2 twice except two of them.
362.915 -> 3 and 2 are not repeated here, but otherwise all the elements are being repeated twice.
368.849 -> You have to find those two elements. So think how you'll solve through the help of XOR.
375.266 -> Think a little, how will you solve with XOR, take your time, pause the video here and try to solve it.
382.85 -> If you have solved it then, its a good thing.
385.605 -> It was a very good question. But if you couldn't then don't take tension, I'll explain you, how you to solve it.
391.386 -> In Bit manipulation, if you know the technique it'll strike at that moment, but if you don't then
400.743 -> in a way, for instance, if you know the puzzle the you answer it very quickly, its of the same type here.
407.193 -> If you know the tricks, then you can do it easily but intuitively there isn't any approach.
414.303 -> So we have learnt a lot of techniques as it's the third video. So we have covered major techniques
419.854 -> after his you can solve the question.
421.488 -> I'll tell you once more. So, if you'll XOR all the no. just like the last question
428.582 -> Then you'll know that the result would be 3^2.
436.771 -> Result would be 3^2, you wanted both of the numbers, right!
441.643 -> Two different numbers, 3 and 2, but if we XOR it the the answer would be 10.
450.271 -> So this is 1, basically 3^2 is 1.
454.543 -> we have got a^b, which means that we have got the XOR of those element which are non- repeating.
460.138 -> rest would be cancelled and you'll only get a^b, if we assume.
465.696 -> We have got a^b ,but we are finding them separately. a^b won't work here.
471.594 -> Now we have to separate them. Right!
474.43 -> How will that be done? So -a^b is 01.
477.418 -> We just have to apply XOR in such a way that one of them will exit and we get the other one.
487.157 -> How will we do it? Let's think.
490.303 -> A little trick will be applied, so watch carefully.
493.809 -> You have already got a^b, now find the bit of rightmost side of a^b.
501.515 -> So this is XOR- 01 the rightmost side bit is this one.
508.293 -> We know the set bit which is 1, which means that they are at this position
514.973 -> these numbers- a and b, they will have different bit, then we have the XOR as 1.
521.728 -> Both of them will be different. We don't know which bit belongs to which no.
525.301 -> We only know that bit will be different for both no., that is why the XOR is 1 on this position.
531.51 -> We have setted it. Now we can divide this whole array in two parts where we'll say that this is 0th position.
541.4 -> At 0th position whose bot is 1 and whose is 0, we'll divide according to it.
547.601 -> How and what is being done, just think about the logic right now. We are building logic.
552.797 -> So we have to divide in 2 parts where the bits are 0 and 1 at the 0th position. S this side we'll put 1 and on the other 0.
560.93 -> So, the odd no. will come towards 1, because the no. at this position is odd number.
568.49 -> So 5 has side bit 1 at 0th position, then 1, 3, has 1 at the 0th position bit, then 5 and then 1 again.
578.957 -> So this is a bucket and second bucket will contain the remaining numbers. which is 4, 4 and 2.
588.114 -> You have two buckets and if you see clearly here, both the numbers have been separated in two buckets
595.065 -> 3 and 2 are separated.
598.229 -> 3 is in the bucket where bit is 1 and 2 is in the bucket where bit is 0.
605.657 -> Alright! Now its still 3^ 2 in the result. XOR this with the result. Store this result in temp.
616.786 -> temp= result, it'll be 3^2.
621.936 -> So its 3^2. Now XOR them with the elements on the left.
626.2 -> 33^2^5^1^3^5^1. So if you see here then, similar no. will be cancelled. 3 wity 3
633.571 -> 5 with 5, 1 with 1 and remaining would be 2.So 2 is separated from 3^2
640.723 -> So this is one of the no., you have got' b'. Now you have to find 'a'.
645.169 -> To find 'a', XOR once again with the result. So it was 3^2
650.971 -> Along with that we'll XOR this one.
652.97 -> 2 will be canceled and we'll get 'b', we'll get 3.
657.362 -> So, a=2 and b =3.
660.106 -> So it would have been interesting to you. You must have had fun. So we can solve the question in this way, basically
666.157 -> There are 2-3 scrap in this question. First take XOR of all the numbers and include it in the result.
670.082 -> We know that others will be cancelled and we'll get a^b.
675.913 -> now we have to find 1 in the rightmost side of the result. We saw that rightmost side bit is 1 at 0th position. OK!
684.941 -> Now, we have divide this array in 2 parts according to the side bit 0 and 1 at 0th position.
694.071 -> So we'll ate the 1's, we don't need the other one right now.
698.563 -> the no. who have rightmost side bit as 1,take its XOR with the result.
702.613 -> So we already have 3 ^2, now we took its XOR with 5, then with1, 3 , 5, 1
712.243 -> After all the operations, you can be certain that, we got one of the numbers, suppose it's 'a'.
722.139 -> Now we have got 'a', you must have done with temp. You know that it's still3^2 in the result, so you'll do XOR it again with 'a'.
732.109 -> then you'll get the other number as well.
735.429 -> So in this way we have easily done this question as well, in the constant space.
740.961 -> It was a very good question.
742.951 -> Now let's move on to the 3rd question , which is a little bit different than these two questions.
747.343 -> Third question says to find the only non- repeating element in a array where every other elements repeat thrice.
753.74 -> So in this questions elements repeated twice, here it's being repeated thrice.
759.948 -> So the question is like this, you have been given an array where each element is repeated thrice, except 5, rest 2 is occurring thrice
770.394 -> And 1 as well. In this way there can be multiple elements.
773.493 -> You have to find the non- repeating element and there can be other variations of this question, which would be the bonus question
781.955 -> That would be - to find the element which occurs once and rest are occurring 'k' times.
788.784 -> For instance here, k=3 and it can k=4, 5....like this,
792.796 -> That could be done easily after this.
797.143 -> Try solving it in a^b method. But it can't be done that way because that method works in binary XOR.
809.572 -> Means if two no. are similar then it becomes 0 otherwise it's something else
815.443 -> Here, either you modify it. You have to make function of 3-array binary XOR
824.15 -> You can do that as well. Or there is a better way with which we are going to solve it.
828.086 -> we'll find on which bits are they located. Numbers are occurring thrice and in which bit- it is occurring 3n+1 times.
838.357 -> If you don't understand then don't worry, basically, you know that any number, if they are inside 'int', then
845.041 -> each number will be taking 32 bit space.
849.2 -> It's of 32 bits, in this way, so suppose this is 2 and its 1 0 , right!
857 -> Its the first number 2 which is 1 0, then at this position
863.171 -> Now 1 is at the first position, so we'll implement 1.
867.58 -> Next will be 2, again 0 is in this position so it won't change and in this position its 1, so we'll say that now its 2.
877.05 -> I am counting, basically ,I have made a count array here.
882.4 -> This is the array of 32 size and with its help we are going to find that number.
888.636 -> And in this count array we are tallying, 1 bit is at which position and how many times for these elements.
896.341 -> Next number is 1, for 1 this bit is 1. Then the next number is 5 which is 101.
904.757 -> For 101, this bit is 1 so this is 2.
908.486 -> then this will be 2 as well, then this bit is also 1 so here it'll be 1.
912.7 -> Next is 1,this bit will change to 3 now. Next number is also 1, so this bit will change to 4
923.786 -> then next on is 2, which is 1 0, this bit would remain as it is, but for 1 it'll be 3.
930.414 -> So we have found it out. Now through the help of this array we can say that it's 5.
937.337 -> Now let's see this. We know that every number is repeated thrice, except one.
946.558 -> That means these numbers- 2,2, 2that is 10, 10, 10. The first position
954.688 -> will be in the multiple of 3, right!
957.289 -> If there'll be extra 1 then that will be 3n+1
963.9 -> In this way we can find that, in which position are they located in then multiple of 3.
967.75 -> So here it's not a multiple of 3, so the remaining is changed to1, because it's 4
973.183 -> So 4 is not in multiple of 3 , then the remaining number will be 1.
977.638 -> This is in the multiple of 3 which means here it'll be 0
981.271 -> This is not in the multiple of 3 so the remaining number would be 0.
985.1 -> You have got- 101, which is 5. You got 101 from this array. Now do you know this?
992.048 -> binary representation is 101, so with it's help you can easily calculate by doing 2^power
997.499 -> So in this way it is solved. Now it's being repeated thrice, if you want you can make it 'k' times repeated.
1004.131 -> If you'll repeat 'k' times then ,here you have to try module of 'k'. Here I did module of 3, you can do 'k'
1012.261 -> If it's in 'k' module, then it'll be 0 at it's place, if not then there will be 1.
1017.877 -> So in this way it gets solved and it has the space O(1). You have taken the array of size 32.
1025.457 -> But it'll be considered of constant space as well.
1028.1 -> So we can solve this question in the constant space, in O(n)
1032.819 -> So, it was a very good concept. I hope you liked it.
1035.287 -> So we saw these questions. After this, I'll give you some assignments
1039.48 -> Firstly, you can easily solve the questions on Interview Bit, solve it once.
1044.091 -> After that, if you want to solve then you can go to Geeks for geeks
1048.8 -> try solving their hard level questions. There might be some questions that would be difficult for you.
1054.943 -> So understand their editorial, if you are watching bits for the first time, then understand their intro
1059.471 -> There can be new concepts. As I told you, if you have read some concepts about bits earlier then it'll click your mind
1067.472 -> and if not, then you have to read it for the first time.
1070.264 -> So, intuitively we can't understand bits quickly, there are lot of tricks in it.
1074.657 -> but when you understand those tricks once, then its easy to solve questions in bits.
1080.725 -> Large questions where we don't understand how will there complexity be reduced, it is reduced with the help of bits
1086.079 -> and its beneficia for competitive programming as its fast as well.
1090.029 -> So, with we have finished the bits. In the next video we'll be talking about next topic.
1094.557 -> today we have completed bits, 3 videos if you liked it then do share it in the Linkedln once.
1099.838 -> If you have learnt a new concept then share that concept in the Linkedln.
