# 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[0]); 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[1] as negative. So our array becomes {2, -4, 1, 4, 3}.

For i = 1, we do the same and mark A[4-1] = A[3] 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[3], 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[0]); 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:-

## Leave a Reply