In Missing Number problem we have given an array of size N containing a number from 0 to N. All the values in the array are unique. We need to find the missing number which is not present in the array and that number lies between 0 to N. Here we see a simple approach for finding the missing number. We just count the total sum of the elements of the array which is given to us. After this, we find the sum of the number from 1 to N and subtract the total sum of the element from it. Then we got the number not present because we only miss that number in the sum of elements.
Table of Contents
Input Format
First-line containing an integer value N.
Second-line containing N integer values.
Output Format
Only one line containing the missing number.
Constraints
- 1<=N<=1000000
- 0<=arr[i]<=1000000
- All numbers in the input array are distinct.
Sample Input: 9 9 6 4 2 3 5 7 0 1
Sample Output: 8
Explanation: Here the total sum of element = 9+6+4+2+3+5+7+0+1 = 37. Now we find the sum of first N natural numbers which is N*(N+1)/2. So, total sum = (9*10)/2 = 45. Now subtract the total sum of the element from the total sum. We got 45-37 which is 8. So our missing number in the input array is 8. Here we just use one variable means o(1) is the space used.
Algorithm
Step:1 Set elem_sum = 0.
Step:2 For i in range 0 to N-1:
elem_sum = elem_sum+arr[i].
Step:3 Total_sum = (N*(N+1))/2
Step:4 print (Total_sum-elem_sum).Implementation For Missing Number
/*C++ Implementation of "Missing Number".*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
/*input values.*/
int n;
cin>>n;
/*set elem_sum to 0*/
int elem_sum=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
/*add the value of x to elem_sum*/
elem_sum+=x;
}
/*print missing number.*/
cout<<"Missing Number: ";
cout<<(n*(n+1))/2-elem_sum<<endl;
return 0;
}13 0 3 2 1 5 6 7 4 9 8 10 12 13
Missing Number: 11
Time Complexity
O(N) where we use one loop for taking input. While taking input we store the element sum continuously. And then use the simple concept of sum of the first N natural number.
Space Complexity
O(1) because we don’t use any extra space and we just take input using variables. Here we use the variable which stores the sum of all the elements present in the array. Another variable store the sum of all the elements from 1 to N. Using these variables only we find the missing number.