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.