# Find the repeating and missing number in an array(C++)

In this post, we are going to find the repeating and missing number in an array in C++. It is a famous question about array implementation. Let us understand the problem first.

## Understanding the problem

We are given an unsorted array of size n. The array elements are in the range 1 to n. But one number from the range {1….n} is repeated and one number is missing. Our task is to find the repeating as well as the missing number.

For example:

A = {2, 4, 1, 4, 3}

Here the size of array n = 5 and the repeating number is 4 and the missing number is 5.

There are many methods to solve this problem. Here we are going to learn about two such methods.

## Method 1

The elements are in the range 1 to n and exactly one number is repeated and missing. Let the number missing be x and the number repeating be y. We find the total sum of all elements in the array as well as the sum of natural numbers from 1 to n which is n*(n+1)/2. We subtract both the sum and get one equation in x and y.

`x-y = sum of all elements of array - sum of n natural numbers.`

Similarly, we find the sum of squares of all elements in array and sum of squares of n natural number which is n*(n+1)*(2n+1)/6 and subtract them. Thus we get another equation in x and y.

```x^2 - y^2 = sum of squares of all elements in array - sum of squares of n natural number
The above equation can also be written as
(x-y)(x+y) = sum of squares of all elements in array - sum of squares of n natural number```

Now that we have two equations and two unknown it is a matter of solving the equations using basic mathematics.

Let us see the code implementation

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void find_missing_repeating(int A[], int n){

long long sum = (long long)n*(long long)(n+1)/2;
long long square_sum = (long long)n*(long long)(n+1)*(long long)(2*n+1)/6;
long long actual_sum=0, actual_square_sum=0;

for(int i=0;i<n; i++)
{
actual_sum += (long long)A[i];
actual_square_sum += (long long)A[i]*(long long)A[i];
}

long long a1 = actual_sum - sum; // x - y
long long b1 = actual_square_sum - square_sum; // x^2 - y^2
long long sum_of_x_and_y = b1/a1; // x + y = (x^2 - y^2)/(x-y)

long long repeating = (a1 + sum_of_x_and_y)/2;
long long missing = (sum_of_x_and_y - a1)/2;
cout << "Repeating number is "<< repeating<<endl;
cout << "Missing number is "<< missing<<endl;
}
int main()
{
int a[] = {2, 4, 1, 4, 3};
int n = sizeof(a)/sizeof(a);
find_missing_repeating(a, n);
return 0;
}```

Output –

```Repeating number is 4
Missing number is 5```

## Method 2

In method 2 we use the elements in the array as index and we mark the visited places. Let us understand it by an example.

A = {2, 4, 1, 4, 3}

We traverse the array elements one by one and while traversing we use absolute value elements and make the value at this index as negative to mark it visited.
For i = 0, we are at 2 and we mark A[abs(A[i])-1] as negative. Hence we mark A[2-1] = A as negative. So our array becomes {2, -4, 1, 4, 3}.
For i = 1, we do the same and mark A[4-1] = A as negative. Thus array becomes {2, -4, 1, -4, 3}
Similarly after i = 2 out array becomes {-2, -4, 1, -4, 3}
For i = 3, when we go to A[4-1] = A, we find that it is already negative, which essentially implies that we have visited this number before. Thus we get our missing number.
For i = 4, our array becomes {-2, -4, -1, -4, 3}.

Now to find the missing element we traverse the array again and search for positive number. Thus the missing number would be index of positive number + 1.

Let us see the code implementation

```#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void find_missing_repeating(int A[], int n){

int repeating,missing;

for(int i=0;i<n; i++)
{
if(A[abs(A[i])-1]<0)
repeating = abs(A[i]);
else
A[abs(A[i])-1] = -A[abs(A[i])-1];
}
for(int i=0;i<n; i++)
if(A[i]>0)
missing = i+1;

cout << "Repeating number is "<< repeating<<endl;
cout << "Missing number is "<< missing<<endl;
}
int main()
{
int a[] = {2, 4, 1, 4, 3};
int n = sizeof(a)/sizeof(a);
find_missing_repeating(a, n);
return 0;
}```

Output –

```Repeating number is 4
Missing number is 5```

That’s it, folks. Thank you for reading the post. Any doubts are welcome in the comment section.

Check out my other blog posts:-