Missing Number
Updated: Jun 25, 2020
Problem Statement -
Time limit: 1.00 s
Memory limit: 512 MB
You are given all numbers between1,2,…,n except one. Your task is to find the missing number.
Input
The first input line contains an integer n.
The second line contains n−1 numbers. Each number is distinct and between 1 and n(inclusive).
Output
Print the missing number.
Constraints
2 ≤ n ≤ 2⋅10^5
Example
Input:
5
2 3 1 5
Output:
4
LOGIC
To solve this problem, we can create two arrays, one that contains input. Now, we can traverse the one which contains input and for each element we make that element’s index as 1 in second array to indicate that this element exists in input.
For example -
If input is 5, we create 2 arrays. Now, let’s name input array as ”a” and second array as “flag”.
Now, traverse ”a”. For a[0] i.e. 2, make flag[a[0]] = 1. This will make index 2(Since a[0] = 2) in flag array as 1 which means 2 is not missing. Similarly, 3, 1 and 5 are also rejected. We are now left with 4 which is missing.
APPROACH
We take two arrays of size 10^6(Because n can go up to 2*10^5) so we don’t run out of memory. Also, we initiate each value in both arrays to 0. We take n as input and take n-1 inputs in one of the arrays.
Now, traverse this input array and for each input_array[i] make flag[input_array[i]] = 1.
Now, traverse the other array and whichever element’s value is 0, that’s the missing number.
CODE(C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll n, a[1000007] = {0}, flag[1000007] = {0};
cin >> n;
for(ll i=1; i<n; i++)
cin >> a[i];
for(ll i=1; i<n; i++)
flag[a[i]] = 1;
for(ll i=1; i<=n; i++)
if(!flag[i])
cout << i << endl;
}
A BETTER SOLUTION
We can just find the sum of first n natural numbers by n(n+1)/2. Then, we can sum whole array and subtract it from first n numbers’ sum. Eg: 5
2 3 1 5
Array sum = 2+3+1+5 = 11
Sum of first 5 numbers = 5(5+1)/2 = 15
Missing number = 15-11 = 4
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll n, x, sum = 0;
cin >> n;
for(ll i=0; i<n-1; i++)
{
cin >> x;
sum += x;
}
cout << n*(n+1)/2 - sum << endl;
}