Find the Missing and Repeating Number | GFG | C++ and Java | Brute-Better-Optimal-Optimal

In case you are thinking to buy courses, please check below:

#dsa #course #placements

[takeUforward]

Drop "Understood" if you did understand, or else drop your doubt portion.. ^ _ ^

.

[tanmaythaker]

This channel is actually taking me forward towards my goal!

[bismeetsingh]

Xor solution is something that even the interviewer wont know.

[_-]

I felt the first solution of this video really good! Other solutions too are good but this was much easy to understand or I'm slow!

[sujan_kumar_mitra]

It's very difficult to remember the xor approach. I could only come up with the summation approach by myself

[aishwaryamajumdar]

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).

[yuvrajoberoi]

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?

[fullysimplified]

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!!!!

[prajjwalagarwal]

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

[nawalrathore]

New name with same energy.... loving it♥️🙏

[twinklebajaj]

I wonder how beautifully someone can come up with such a crystal clear explanation! Hats off to you! Huge fan sir ! :p

[ayushmandloi]

in XOR approach we are actually using 0(2N) space, that baskets . so hashing could be more optimal

[jaiminsolanki]

Understood Brother...
Thank you for playing such a vital role in making our career!

[growmore]

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<n;)
{
if(arr[i]==i+1)
{
i++;
}
else
{

if(arr[arr[i]-1] == arr[i]) i++;
else swap(arr[i], arr[arr[i]-1]);
}
}
// traverse the array and find which
// element is not at its correct place
int missing = 0;
int repeating = 0;
for(int i = 0;i<n;i++)
{
if(arr[i]!=i+1)
{
missing = i+1;
repeating = arr[i];
}
}
int *ans = new int[2];
ans[0]=repeating;
ans[1]=missing;
return ans;
}

[divyanshupandey]

i really got motivated after seeing even after getting placed you teach more than i study thanks for the lectures

[awalktoinfinity]

1:39 thoda galat ho gya.. how come 2 is missing since 2 is present, 5 is missing na.. anyways itna chlta h :)

[rryann]

A M A Z I N G effort from you! A real thank you from the bottom of my heart! Please continue the whole process ! Much appreciated

[naro.tam_]

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

[sarahdaniel]

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.

[vigilanthuman]

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?