Find the repeating and missing number in an array(C++)
By Prayas SambhareIn 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