Find missing and repeating number

This video explains how to find missing and repeating number in an array. I have shown 3 methods. The first one is naive approach which is done using sorting technique. The second one is better which makes use of buckets or hashing. The third one is the efficient approach which makes use of mathematical formula or tricks. Code is explained for the better approach at the end of the video so do watch till the end. CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[ayushparikh]

i feel this explaination is much better than striver's video, thanks a ton !

[prabhavagrawal]

This is the best explaination, I've seen. Solved most elegently !

[pavanala]

Very useful channel for coding interview preparation..❤️❤️

[yashpreetbathla]

MUCH NEEDED VIDEO ❤️❤️ Awesome explanation keep uploading :))

[pendyalaabhishek]

nice content bro . by the way I am also metallurgist turned programmer . still in b tech 4th year trying to get a software job . your videos helped me a lot .

[sanskarkumar]

Sir huge respect For You. Your videos are literally great and help us understand the code even better. But I have a suggestion for you. As you did in this Video like explaining the Code at the last. You should do it in all your videos. I Know that you arr doing it in your Leetcode april challenge videos. You should also do it your other videos as well. I truly appreciate Your efforts. And Wish For Your Good Luck.

[letsdoeverythinginoneweek]

sir ur explanation is great thank u for such nice explanaiton

[ravinasardar]

Can u tell. Me how did u give input to code?

[harshpatel]

sir your video will help to crack coding interview. plz not stop putting video in future

[anjalisingh-sxct]

Space complexity of bool array/2 method is O(n+1) or O(n)???

[arunlachheta]

it was nice and so much helping, but can u explain it by using xor method

[sarcaastech]

please make a video on the XOR approach also

[mahipalsingh-yojt]

A better solution of o(1) space and o(n) time complexity is to use absolute values of indexes to mark them negative. And if it is already negative, then the number is repeating.

[mdsameershaikh]

How to learn arrays in DSA plzzz suggest me??

[nikhil.pandey]

have you seen interviewbit's solution? although they are also using the same approach but they somehow preventing themselves from large arithmetic values?
please help if you understand ? following is there code.

vector<int> repeatedNumber(const vector<int> &V) {
long long sum = 0;
long long squareSum = 0;
long long temp;
for (int i = 0; i < V.size(); i++) {
temp = V[i];
sum += temp;
sum -= (i + 1);
squareSum += (temp * temp);
squareSum -= ((long long)(i + 1) * (long long)(i + 1));
}
// sum = A - B
// squareSum = A^2 - B^2 = (A - B)(A + B)
// squareSum / sum = A + B
squareSum /= sum;
// Now we have A + B and A - B. Lets figure out A and B now.
int A = (int) ((sum + squareSum) / 2);
int B = squareSum - A;
vector<int> ret;
ret.push_back(A);
ret.push_back(B);
return ret;
}

[SomnathDas-fgqc]

sir can u provide a code for the third approach, how we will implement mathematical terms into code

[corruptmind]

Can you explain how traversing from left to right will be O(N log n)?

[growmore]

one more approach(easy):
gfg all test cases passed.

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;
}

[shloksoni]

What do you use to write? software + hardware?

[zss]

I really like the optimal solution, but the formula for sumN and sumN^2 seems like a very special case...

This is an idea from your other video which is using division/modulo to store 2 numbers in a single array slot.
This is an optimization on your second approach in this video which should also result in O(1) space, but you won't need to care about squaring the number.

we first pick a key which just needs to be 1 bigger than the max in the array.
we then traverse the unsorted array, add the key to the element (as true/false flagging)
(I would copy the following into a text editor for highlighting)
```python
arr = [] # define your input here

key = len(arr)+1 # this is assuming input is from 1 to n
for num in arr:
# because we are modifying the array, we need to check
if num > key:
storeIndex = num-key-1
else:
storeIndex = num-1 # if we assume the min of input array is 1

if arr[storeIndex] < key:
# it means it's unvisited
arr[storeIndex] += key
else:
# it means it's visited and repeated
repeat = storeIndex+1

# we have the repeated number, now we restore the array and find missing
for i in range(len(arr)):
if arr[i] < key:
missing = i+1
else:
arr[i] -=key

print('repeated: ' + str(repeat))
print('missing: ' + str(missing))
```
as an example, [3, 3, 4, 2, 1] as input, we choose 6 as key, applying the key: [9, 9, 10, 8, 1]
the index where element is smaller than key is the number missing (5th index)

I had a bug in the code, this is a debugged version