similar question was asked me in the interview like : given array of elements from 141 to 240 of an unsorted array. in this array, 2 numbers are missing ... find those two numbers with Max time complexity: O(N) .. N is the size of the input array.
This same solution is everywhere throughout the net, it seems like every other ds/algo youtube channel came with the same solution. How do we get the intuition to use xor? Can you provide some other problem similar to this where xor can be used so that we understand how to approach the problem better.
Have added link to "1 number missing" question in description. I couldn't find the "2 numbers missing" question on LeetCode/Hackerrank but I have personally experienced this question being asked a lot and it is present on geeksforgeeks. Since it requires just an array input, I recommend you to practise it on any ide you are comfortable with :)
Hello, So in the interview is it fine if we do not derive any solution and just use this pre derived formula and solve the problem? I mean there is no reasoning we can give why this works.
Hi Keerti , nice explanation, have a query from the interviewer perspective, do you really expect a candidate to solve this in interview if he hasn't seen the question before ?
Yaar didi aaap itna accha pdhati ho.. Koi course hota na Mai pkka le leta.. ❤❤❤ Didi itna bdhia padhaya yh aapne .. Didi ek dikkat h maine aapse Median of sorted array bhi smjha tha 2-3 mahine phle tab sab smjh aya lekin ab mai code nhi krpaunga aisa kyu😔... How to deal with this Please
I have a more intuitive solution that uses O(N) time complexity and O(1) space. The drawback is that in my opinion her concept sounds cleaner. but this approach is good too; read below: We have an array of N elements in range(1, N) and 2 elements are missing how do we find the values of the 2 elements? The idea behind this method is that it leverages on the fact that the array is in range (1,N) elements. So we can use the indexes of the elements and find the elements that are missing. As we traverse the array the value of an element at an index we negate the element at the corresponding index that equals that value. When we are done we traverse the array again looking for positive elements any positive element we find its index is a missing element. Now the part that makes me say its a draw back is that before we do the above we have to traverse the array looking for N-1th element and the Nth element because we do not want to get an index error in our array. let me give an example to make everything clear. A = [3,1,5,6] This array A is in range 1 - 6. We traverse looking for 6 and 5 . We find both 6 and 5 in the array. Why do we look for both of them first? because looking for A[5-1] or A[6-1] would give us an error. So we continue we traverse the second time A[0] == 3, A[3-1] ==5 we negate 5 , next iteration A[1] == 1, A[1-1] == 3 so we negate 3 next iteration A[2] == 5 since we get 5 we skip to next iteration because it would give us an error. next iteration A[3] == 6 since we get 6 we skip to next iteration and then we're done. so our array would look like this A = [-3, 1, -5, 6]. Now since we have this array we traverse once more looking for positive numbers any positive number we find its index is a missing number. so the index of 1 and 6 are the missing numbers. 2 and 4. Take note of the zero-error because numbers start from 1 not zero.
how just by classifying the numbers based on right most set bit helps in finding the number i did not understand it logically please can anyone explain
Thank you for the video. Would've really liked to see you implement the brute force approach and talk more about how you would figure out the missing number using hash map or vector as you didn't mention how you would keep track of which number was missing given an unsorted array.
[JAVA CODE] public class Main { public static void main(String[] args) { int []arr = {1,2,4,6}; int n = arr.length+2; int asum = n*(n+1)/2; int csum = 0; for(int ele:arr) csum+=ele; int diff = asum-csum; int avg = diff/2; int firstele = 0; int secele = 0; for(int i=1;i
was looking for solution of missing and repeating number and this video gives the approach of that as well.
I found this channel today. I absolutely loved your explanation.
Thanks for introducing new weapon called xor.
similar question was asked me in the interview like :
given array of elements from 141 to 240 of an unsorted array. in this array, 2 numbers are missing ...
find those two numbers
with Max time complexity: O(N) .. N is the size of the input array.
Was looking for solution of missing repeating number and this video gives the apporach as well.
🥰 grt approach, another similar type ques is find one missing and one repeating number in array.
Found great video after a long time on DS. Explanation is very good and to the point. Thanks for posting, keep going! 😃
Thank you so much Abhijeet 😇😇
one video with so many approaches simply great. ☺
I fall in problem suru m smz aa rha tha bt last tak aate aate mujhe ghar jane do wali condition aa gyi bt I appreciate ur efforts thanks
Well Explanation is good but if you can show us how can we implement these logic in the code it will give the viewer better understanding.
Thank you for this video, the explanation helped solidify my understanding of XOR.
The xor concept is interesting but how can we implement in program? Explain the same in writing program or send program link if already there.
Suppose the input array had negative elements e.g. A{1, -2, 4, -5, 6} how would you find a missing element?
Your input is invalid, it should have elements from 1 to n with 1(or 2) elements missing
This same solution is everywhere throughout the net, it seems like every other ds/algo youtube channel came with the same solution. How do we get the intuition to use xor? Can you provide some other problem similar to this where xor can be used so that we understand how to approach the problem better.
You can try the problem, in an array every number appers twice except two. Find the two numbers which appers once.
The moment I saw the video I could recognize her from the Google Interview video she gave which was so good!
Thank u mam nice explanation of this problem solution and again thank u for making this video..
Keerti you nailed it. tremendous explanation!!!!!
Please make more videos like this👌👌
Can we extend your solution for finding 3 missing numbers?
Nice Explanation
Nice explanation. I would not have thoughts of it
Like the way you started with simple solutions and loop holes in that and keep on improving solution. Good work for bringing up such video!
Thanks, this is how we can really build the thinking process for interviews 😇
Great explanation! Also, could you please share the link of a question using this concept, so that we could implement the logic. Thanks. :)
Have added link to "1 number missing" question in description. I couldn't find the "2 numbers missing" question on LeetCode/Hackerrank but I have personally experienced this question being asked a lot and it is present on geeksforgeeks. Since it requires just an array input, I recommend you to practise it on any ide you are comfortable with :)
@@KeertiPurswani Thanks, will surely practice. :)
The averag of 2 and 4 is 3. 2 is smaller than 3 and 4 is bigger 🙂
Nice explanations..
Thanks for great explanation👍
Hello,
So in the interview is it fine if we do not derive any solution and just use this pre derived formula and solve the problem? I mean there is no reasoning we can give why this works.
thanks for the upload
Hi Keerti , nice explanation, have a query from the interviewer perspective, do you really expect a candidate to solve this in interview if he hasn't seen the question before ?
Nice explanation.
int arr[] = {2,3,4}; for this array how first approach is valid ?
Thanks a lot , One of the best class
you have done great work
Learnt something new today
great explaination thank you
Glad you liked it :)
Yaar didi aaap itna accha pdhati ho.. Koi course hota na Mai pkka le leta.. ❤❤❤ Didi itna bdhia padhaya yh aapne .. Didi ek dikkat h maine aapse Median of sorted array bhi smjha tha 2-3 mahine phle tab sab smjh aya lekin ab mai code nhi krpaunga aisa kyu😔... How to deal with this Please
I have a more intuitive solution that uses O(N) time complexity and O(1) space. The drawback is that in my opinion her concept sounds cleaner. but this approach is good too; read below:
We have an array of N elements in range(1, N) and 2 elements are missing how do we find the values of the 2 elements?
The idea behind this method is that it leverages on the fact that the array is in range (1,N) elements. So we can use the indexes of the elements and find the elements that are missing. As we traverse the array the value of an element at an index we negate the element at the corresponding index that equals that value. When we are done we traverse the array again looking for positive elements any positive element we find its index is a missing element. Now the part that makes me say its a draw back is that before we do the above we have to traverse the array looking for N-1th element and the Nth element because we do not want to get an index error in our array. let me give an example to make everything clear.
A = [3,1,5,6] This array A is in range 1 - 6. We traverse looking for 6 and 5 . We find both 6 and 5 in the array. Why do we look for both of them first? because looking for A[5-1] or A[6-1] would give us an error.
So we continue we traverse the second time A[0] == 3, A[3-1] ==5 we negate 5 , next iteration A[1] == 1, A[1-1] == 3 so we negate 3 next iteration A[2] == 5 since we get 5 we skip to next iteration because it would give us an error. next iteration A[3] == 6 since we get 6 we skip to next iteration and then we're done. so our array would look like this A = [-3, 1, -5, 6]. Now since we have this array we traverse once more looking for positive numbers any positive number we find its index is a missing number.
so the index of 1 and 6 are the missing numbers. 2 and 4. Take note of the zero-error because numbers start from 1 not zero.
Superb...
how just by classifying the numbers based on right most set bit helps in finding the number
i did not understand it logically
please can anyone explain
Thanku so much 💕
but how code this in java
Hi , thanks for the explanation , do we have to have number starting from 1 or can it be find missing 1 number from (90,91,94,93) as well ?
please read the question you will understand the context.
the second method of finding two missing number is valid for unsorted array...???????????
yes
Video is really great. Please make tgese kind of videos so that it will be helpful.
For sure. So many coming up!!😇
It would be great if you create git
Please please explain the code of XOR , I can't find its explanation anywhere on YT.
Added to my list!
Watch with 1.5x and skip till 00:08:00 for the best solution.
learned something new today
Mission accomplished 🙂
amazing
Thank you for the video. Would've really liked to see you implement the brute force approach and talk more about how you would figure out the missing number using hash map or vector as you didn't mention how you would keep track of which number was missing given an unsorted array.
Here iam again 😂 in search of xor concept this time
i still have a confusion how you calc N ?
can you explan in code
Why u dont show the code
We are not looking for mathematical logic
Keep it up
6:33 not true what if i take out 1 and 3 from 123456?
Why are you taking out 1 and 3? I am talking about 2 numbers and their average at 6:33🤷🤷
Nice explanation Keerti. I wouldn't have thought of XOR approach.
theory toh de dete ho par code kaha hai
XOR u beauty 🔥mast one mam❤️👍
Thanks Siddharth 😊😊
Code bta dimag to mene lga liya tha kese hoga ,code nhi aata 🤦🤦🤦
i am your new subcriber mam or sister..
Great video!
Thanks 😇
[JAVA CODE]
public class Main
{
public static void main(String[] args) {
int []arr = {1,2,4,6};
int n = arr.length+2;
int asum = n*(n+1)/2;
int csum = 0;
for(int ele:arr) csum+=ele;
int diff = asum-csum;
int avg = diff/2;
int firstele = 0;
int secele = 0;
for(int i=1;i
Book pad rhi ho ?
Who the he*k marked this question easy on Leet Code?
do the programs in such a way user gives the input
What do you mean?
@@KeertiPurswani instead of taking direct values use user defined for other programs
@@KeertiPurswani can u make video on functions and recursion's with examples
Are you sindhi?
Yup!
damn she bad
But mam, you started with finding 2 missing numbers. Please upload