Missing Number

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;  
}