Missing Number

Missing Number

Ramandeep Singh's photo
Ramandeep Singh
·

1 min read

You are given all numbers between 1,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

Input:

5
2 3 1 5

Output:

4

Solution:

It is easy to solve this problem, as only one number is missing then we focus on the difference, the difference is only of one number, all we have to do is just sum up all the numbers from the given series and then subtract this number from (n*(n+1))/2;

because (n*(n+1))/2 represents the sum of all numbers from 1 to n.

That's all we have to do for this.

Let's code the solution

#include<bits/stdc++.h>
using namespace std;

int main(){
       int n;
       vector<int>v(n-1);
        int sum = 0;
       for(int i=0;i<n-1;i++)cin >> v[i], sum += v[i];

        cout << ((n*(n+1))/2) - sum; 
}

See you in the next blog article :)

DSAarticlesBlogging