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.
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.
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.
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 ?
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.
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
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
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.
[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
