Missing Number

Updated: Jun 25

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



Recent Posts

See All

Increasing Array

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the

Repetitions

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence.

Weird Algorithm

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorith

©2019 by EduGeekX. Proudly created with Wix.com