Find missing number in array of continous integers.

June 23, 2019

In the given array of size n, we have n-1 integers and these integers are in the range of 1 to n. Our aim is to find the nth number which is missing from the array. Although, we assume that they are no duplicates in the array.

Example
n=9,(which denotes the size of the array.)
a[]={1 ,2 ,3 ,4 ,5 ,7 ,8 ,9}
the output for the following input array must be 6

Logic:-

First of all what directly clicks is we can traverse the array and find the missing number, but certainly its more time-consuming.Since there are n integers in the array thus we can use the sum formula to find the sum of first n integers. The sum of integers in an array can be found in a single traversal.
Thus the difference between calculated sum and sum of the array is the number missing from the array.

Sum of First n integers is given by = n(n+1)/2

code

[code language=”cpp”]
#include <iostream>
using namespace std;
//program to find missing number from array of n integers
int main() {
// your code goes here
int n,i;
cin>>n;
int c_sum=n*(n+1)/2;// the calculated sum using the sum formula for first n integers.
int a[n-1];
int sum=0;
for(i=0;i<n-1;i++)
{
cin>>a[i];
sum=sum+a[i]; // sum of elements in array.
}
cout<<c_sum-sum<<endl;// output the value of difference between the calculated sum and sum in array
return 0;
}
[/code]

Above code is based on the logic of sum of first n natural numbers.As a result, we can find the missing number from an array of first n integers.
Readers are advised to submit their self- written codes in the comment section below.

3 comments on “Find missing number in array of continous integers.”


  • Peeyush

    #include
    using namespace std;
    int main(){
    int a,sum=0,r,q;
    cin>>a;
    int p[a];
    for(int i=0;i>p[i];
    sum+=p[i];
    }
    r=(a*(a+1))/2;
    q=r-sum;
    cout<<q<<endl;
    }


  • Abhishek

    #include
    using namespace std;
    int miss(int a[],int n)
    {
    int total=(n+1)*(n+2)/2;
    for(int i=0;i<n;i++)
    {
    total=total-a[i];
    }
    return total;
    }
    int main()
    {
    int a[]={1,2,3,4,5,7};
    int n=sizeof(a)/sizeof(a[0]);
    cout<<miss(a,n);
    return 0;
    }