Find the Missing and Repeating Number | 4 Approaches 🔥

We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.

You can follow me across social media, all my handles are below:

0:00 Introduction of Course
00:20 Problem Statement
01:14 Brute Force approach
02:08 Pseudocode
03:18 Complexity
03:47 Better approach (Hashing)
05:41 Code
06:58 Complexity
07:28 Optimal approach (Maths + XOR)
08:01 Solution-01 (Maths)
08:08 Intuition + Approach
14:54 Code
19:17 Complexity
19:55 Solution-02 (XOR)
20:15 Intuition + Approach
31:11 Code
41:24 Complexity

[takeUforward]

Note: Please don't use the given array to solve the problem, modifying the input is highly discouraged in an interview.

Why? Imagine I give you user data, and ask you to do a task for me using that data, will you modify that data in order to do it? No right, unless I ask you to do so, then only you should.

[anshumaan]

Same question @leetcode : *Set Mismatch* 🙂🙂

[NoBakwas]

To those whose testcases are failing on gfg and coding ninjas, you need to make sure the 'n' being used in formula is actually in long long format. The 'n' given to us is in 'int' format, so just create a variable 'long long N=n' and then use this 'N' in place of wherever 'n' was used.

[deepakagrawal]

I am hear to teach you problem solving. Thats a great saying bother. It actually motivates a lot to look from the point of view of being a great engineer and solving complex problems rather than preparing from interview perspective. Good one

[Mangesh_]

Bro, usually I don't do comments in any videos ..but this video's forces me to do...top notch content, understood all the 4 algorithm!!❤🎉

[crazyxyzk]

Hy sir as you already know that our summer holidays are started, so I request you to please increase the frequency of upload 🙏🙏

[thenikhildaiya.]

This problem is available on leetcode with name "Set Mismatch". Thoda story based question hai but exactly same hai😊

[captureitall]

I saw differnt youtubers doing a negation method by mofying the given array which is so wrong just loved this explanation by striver bhaiya 🔥🔥❤❤

[pulkitgupta]

Hey I found one more optimal approach in O(n). This also uses some maths

int n = a.size();
int sum = 0;
int p;

for(int i=0; i<n; i++){
sum+=abs(a[i]);

if(a[abs(a[i]) - 1] < 0){
p = abs(a[i]);
}else{
a[abs(a[i]) - 1] = -1 * a[abs(a[i]) - 1];
}
}


int total = n * (n + 1) / 2;
int q = total - sum + p;

return {p, q};

It uses the concept that the array contains only numbers from 1 to n. That means if any index is visited twice then that index will be the value of p. So i keep track of visited indexes by marking thaem negative. And for q i found the sum and applied some basic maths to find it. Once i found p it was easy. I hope this solution also works. Thanks Striver because of you i was able to form this solution on my own ❤❤

[mano_]

Hey striver lots of love and support for u ❤❤ u r doing such a great great work for us thanks a means a lot

[habeeblaimusa]

Bro, I noticed that majority of the array question in the medium and hard part optimization involves hashing. Like 70%..

[gorantlakarthik]

There would be one more optimal approach.. since the values all could lie between 1 to N including both, and indexes are from 0 to N-1. You can find arr[i] and swap it with arr[arr[i]-1] (since index would be 1 less the value in it), and increment the ptr... thus in any case if you find that arr[i] and arr[arr[i]-1] are equal. then arr[i] is the duplicate element, and then finding duplicate element is easy using both sums(S, Sn). The mentioned two methods were good and cool as well.

[culeforever]

understood, will come back later to understand the last approach :)

[shubhamagarwal]

#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.

[sukhpreetsingh]

Thanks a lot for this amazing content. I would like to share one more approach using modulo operator by placing each number at its correct position==>
#include <bits/stdc++.h>
pair<int, int> &arr, int n)
{

int i=0;
while(i<n)
{
if(arr[i]==i+1) i++;
else{
int index=arr[i]-1;
if(arr[i]==arr[index]) {i++; continue;}
swap(arr[i], arr[index]);
}
}

pair<int, int>v;
for(int i=0;i<n;i++)
{
if(arr[i]!=i+1)
{
v={i+1, arr[i]};
}
}
return v;
}

[priyadarsinipaikaray]

Master blaster ❤ your explanation is very clear and we understand it very well ❤ thank you for such efforts 🙏

[pushankarmakar]

BRUTE FORCE:

num=[0]*(len(a)+1)
for i in range(len(a)):
num[a[i]]+=1

for i in range(len(num)):
if i==0:
continue
elif num[i] > 1:
P=i
elif num[i]==0:
Q=i
return [P, Q]

[nostalgiccringeallhailchel]

Time complexity :- O(nlogn) with the xor method.
space complexity :- O(1)
Used the property
a ^ b = c
a = c ^ b

logn is for finding the repeating number by having a counter to traverse through the array.

class Solution{
public:
vector<int> findTwoElement(vector<int> arr, int n) {

int x = 0, y = 0;
for(int i = 1; i <= n; i++) {
x = x ^ arr[i - 1];
y = y ^ i;
}
int sum = x ^ y;

sort(arr.begin(), arr.end());
int repeating = -1;
for(int i = 0; i < n - 1; i++) {
if(arr[i] == arr[i + 1]) {
repeating = arr[i];
break;
}
}

int missing = sum ^ repeating;

return {repeating, missing};
}
};

[Manishgupta]

THe XOR method it tough to understand but the method is really helpful to understand the bit concept. And a very optimal approach.

[anuplohar]

Because of YOU I understood the XOR method very easily
Thanks Striver Bhaiyya