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

Your email address will not be published.