Please watch the new video which covers it in more depth, and also prints it: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-2D0D8HE6uak.html Drop "Understood" if you did understand, or else drop your doubt portion.. ^ _ ^ Code link: takeuforward.org/data-structure/find-the-repeating-and-missing-numbers/ . If you appreciate the channel's work, you can join the family: ru-vid.com/show-UCJskGeByzRRSvmOyZOz61igjoin
you should try to named your channel as a portion of your channel name should have something from computer science or competative prog or ds and algo this will help to grow your channel fast , and your videos will appear in searches with any genral term of computer science as exam i found a channel named algods while i was sarching for some algorithm ananlysis topic.
If the Array 1 is : 1 1 2 3 5 6 and the Array 2 is :- 1 2 3 4 5 6 Xor both of them you will get 1^4 = 101 , so the right most bit which is 1 is 2nd bit is considered that Xor of the first set will give -> missing number and the xor of the second set give-> repeating number, but if we consider the first set bit which is 1 from left which is at the 0th position , the first set will give -> repeating number second set will give -> missing number why this is happening?
We could also use a bit mask (of size N) and set the indexes which are (arr[i] - 1). When an index is set in the mask already, it means that is the duplicate element. We traverse through the mask to see which index is unset and output that index + 1 as the missing element. Time- O(2N) ~ O(N) and Space - O(1).
How come space is O(1), what if we have numbers like 10000, then you have to create a huge mask, which cannot be stored and you have to eventually create an array
another better approach is: int[] findTwoElement(int arr[], int n) { int[] res = new int[2]; long totalN = (long) n*(n+1)/2; long sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } for (int i = 0; i < n; i++) { int remain = n - Math.abs(arr[i]); if (arr[remain] > 0){ arr[remain] *= -1; }else{ res[0] = Math.abs(arr[i]); } } sum = sum - res[0]; res[1] = (int) (totalN - sum); return res; }
Can you cover up more no. of questions in a single video? The interview process has been started by many companies. it will be helpful for us to complete them in short period of time. Otherwise your channel is awesome :D
@i've abandoned myChild Be in your limits sir. I asked if he could cover up more questions in a single video not asking for solutions. So better you mind your own business.
Bro, I did this question before and stopped at the summation soln as it was optimal. I think if I tell the xor soln the interviewer would be sure that I had already done the question. Will it be a bad thing, as he may say that if you had known the soln then you should already tell the most optimal approach and save time for both of us?
Really a very important question. Striver, please do try to answer this. Becoz if we tell such solutions like the last one, it doesn't show our logical/thinking ability because no one can get such a solution by himself. Moreover, it may create a bad impact on the interviewer that we have mugged up the solution. I was getting this doubt a lot of times while preparing...
@@anshumandas5392 Yes, the question is a really good one. I was also asking this to myself for quite sometime. I didn't find any answer. Please reply to this bro.
Thing is both interviewer n interviewee know that questions are repeated, but never reveal it to the interviewer that you have faced the exact same problem before. If they were to ask you that, say that you have faced a similar problem before and always go from brute to optimal. Mostly stick with the square solution unless the interviewer really wants you to optimise the overflow condition, most cases they won't.
This one is too good. I saw this video earier and left it as I was not able to grasp the whole logic that time Saw this question again today and I knew where to go to learn the logic Thanks a ton!!!!
1. Sum of n integers - sum of all array elements. 2. Find repeating element through sorting and add it to the answer got from 1. This gives the missing element. Eg. {4,3,6,2,1,1}; 1. 21-17=4; 2. 4+1=5; 1 is repeating and 5 is missing. Let me know if this approach is correct for all edge cases.
xor of same number result in zero. leaving behind the different number! take an example 1231234 in the array if u want to find out the number which have only one occurrence.. simply xor them you'll end up with 4 only! since x*x=0 where x=1,2,3. Here in the question (4,3,6,2,1,1) if u xor them with 1 ton meaning (443^6^2^1^1]*[14243444546] same number gets cancel results in num= [1^5] and which u have to compute the missing number and repeating one! soo to find 1 and 5 u have to do the remaining step!
A similar problem- wap to find unique number in an array of n numbers in which except one (unique number) rest all are present thrice! i/p = [1,2,3,1,2,3,4,1,2,3] o/p = 4
I have explained the XOR method in detail with the help of an example. You can check the link - github.com/zeph0yr/Competitive-programming/blob/master/Striver's%20SDE%20sheet/Day:1%20(Arrays)/Find%20Repeat%20and%20Missing%20Number.cpp
xor of same number result in zero.. leaving behind the different number! take an example [1,2,3,1,2,3,4] in the array if u want to find out the number which have only one occurence.. simply xor them you'll end up with 4 only! since x^x=0 where x=1,2,3... Here in the question [4,3,6,2,1,1] if u xor them with 1 to n meaning [4^3^6^2^1^1]^[1^2^3^4^5^6] same number gets cancel.. results in num= [1^5] and which u have to compute the missing number and repeating one! soo to find 1 and 5 u have to do the remaining step!
A similar problem- wap to find unique number in an array of n numbers in which except one (unique number) rest all are present thrice! i/p = [1,2,3,1,2,3,4,1,2,3] o/p = 4
learn basics of bit masking then it be very easy to understand and only then it makes sense. it took me 2 days to completely understand and code this problem. theirs a webinar by prateek narang on bit masking go watch it you will be able to understand this q.
I have explained the XOR method in detail with the help of an example. You can check the link - github.com/zeph0yr/Competitive-programming/blob/master/Striver's%20SDE%20sheet/Day:1%20(Arrays)/Find%20Repeat%20and%20Missing%20Number.cpp
one more approach(easy): gfg all test cases passed. TC - o(n) SC - o(1) int *findTwoElement(int *arr, int n) { // fill all elements of arr at position as // according to sorted manner // ex:: 3 2 1 2 after this 1st for loop changes to // 1 2 3 2 for(int i = 0;i
Take one bucket only then you will get one of (missing and repeting) element then xor it with the previous xor result we got that is missing^repetting.You will get 2nd number. No need to take 2 buckets
if we present the xor solution to the interviewer he would know that we have already see this problem and we were acting all along that we aren't working our way into the solution . So, doesn't it impact negatively on us ?? And on GFG there is a solution which take O(2N) time comp & O(1) space comp and it also seems bit more approachable in a interview So i think you should add that or mention that sol. in description or smthing BTW great course, love how you explain, thank you for your work
How can you know an algorithm without reading it? Everything is read previously, its just how you present! Also many programmers can figure this logic if they are deep into cp!
@@takeUforward Ok so all boils down to the way of presentation and Thanks for the prompt reply, Well just a new series suggestion from my side "mock recorded interview with white board showcasing not the problem but the way of presenting different sol.s and also dealing with tricky situation you might have faced in your interview exp. "
yo guys in the solution in which we make two equations can be optimised by using a simple trick. Insted of separetely calculating the sum of elements of array and sum of squares of elements of array separetely (which can cause problem if there are large elements in the array) we can simultaneously add and subtract the corresponding elements of the array and the actual array with elements like 1,2 ,......n; Here is the code hope it helps arrayvector Solution::repeatedNumber(const vector &a){ int n = a.size(); long long sqSum = 0; long long sum = 0; for(int i=0;i
If the Array 1 is : 1 1 2 3 5 6 and the Array 2 is :- 1 2 3 4 5 6 Xor both of them you will get 1^4 = 101 , so the right most bit which is 1 is 2nd bit is considered that Xor of the first set will give -> missing number and the xor of the second set give-> repeating number, but if we consider the first set bit which is 1 from left which is at the 0th position , the first set will give -> repeating number second set will give -> missing number why this is happening?
Order of the container i.e first container gives missing no or repeating number doesn't matter because in the end we will traverse the arrey and check with both the missing and repeating number to find which one is missing or one which is repeating
Two buckets will take up the space of O(n) and have time complexity of O(n), then why not hashing solution? It has time complexity of O(2n) and space complexity of O(n) ? Which is better?
Striver do make these kind of video, i never like or subscribe a channel but urs is an obvious one, plssss make more of these interview related videos.
@@subhajitdas2784 by having the summation of array and subtracting it with sum of 1 to n....by this we have repeating - missing element=diff.......and since we have repeating num via slow and fast cycle detection method we can directly use this equation and find the missing element
@@Whirlwind03 bro the problem you submitted at leetcode is different, please read the problem statement here carefully ! What you are doing is for missing number and no repeating ! Read the problem statement clearly bro !
hey I understood all the optimal solutions, but I don't understand why the 3rd solution is more optimized because it takes O(5N) while the 1st one took only O(2N). so according to time complexity, 1st solution should be the more optimal solution
1st approach takes O(n) time and space complexity while the 3rd approach takes O(5n) (which is considered overall O(n)) time and O(1) space complexity , so , 3rd approach is much more optimized
Sir when I am running my code in VS Code it works perfectly fine but when it is not passes all the cases in the interview bit #include #include #include using namespace std; class Solution { public: vector repeatedNumber(const vector &A); }; bool compare(int a, int b) { return a < b; } vector Solution::repeatedNumber(const vector &A) { vector vr(2); // creating a vector of size 2 vector vrc(A.size()); for (int f = 0; f < A.size(); f++) { vrc[f] = A[f]; } sort(vrc.begin(), vrc.end(), compare); // sorting the vector for (int i = 0; i < A.size() - 1; i++) { if (vrc[i] == vrc[i + 1]) { vr[0] = vrc[i]; } } for (int i = 0; i < A.size(); i++) { if (vrc[i] != i + 1) { vr[1] = i + 1; break; } } return vr; } int main() { const vector v1{4, 1, 2, 5, 3, 6, 7, 8, 9, 10, 11, 12, 12}; Solution s; vector vr2 = s.repeatedNumber(v1); for (int x : vr2) { cout
The separation of the numbers into two buckets in last method is not only going to take O(n) time but also 0(n) space. Isn't it? So, Isn't the hashing approach much more better?
Please read the other comments, this has been answered. Also try to check the link in the description. You don’t need bucket, since at the end you are doing a xor... use two variables to keep the updated xor, that will help!
Bhaiya I have one more approch . time complexity- O(2n) space- O(1) but in my approach I am changing arr[i] to -arr[i]. will this be considered as good approach.
Hello, Hashing, swapping at correct position and using xor . These are 3 approaches which is the 4th one? as u said in start of video if we tell all 4 solution
I have solved this using DFS by placing element into their respective positions and finding the repeating element and then simply traversing the array to find index not having correct element(missing number).
If modifying the input array is allowed, your method or swap sort is great approach, but this is not the case, as input array can't be modified, and creating a copy will take O(n) space.
An other approach is that we choose value and go to that index then minus it if it allready Minus then it's a repeat number and at last positive num is our missing num
is there any significance of taking the right most set bit for dividing in two buckets??..if possible reply. i mean if taking any other bit is going to create any error.?
I use the Negative element approach but I also make array elements +ve again. int[] findTwoElement(int arr[], int n) { // code here int rep = -1; int miss = -1; for(int i = 0; i < n ; i++) { int abs_v = Math.abs(arr[i]); if(arr[abs_v - 1] > 0) { arr[abs_v -1] = -arr[abs_v -1]; }else { rep = abs_v; } } for(int i = 0 ; i < n ; i++) { if(arr[i] > 0) { miss = i+1; }else { arr[i] *= -1;//making positive again } } // System.out.println(Arrays.toString(arr)); return new int[]{rep,miss}; }
