Missing Number Solution

25 April 2021

Statement

( The original statement can be found here )
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
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
5
2 3 1 5

Output :
4

Solution

There are several solutions to this problem including sorting and searching to find the missing number. Even though those solutions are valid I will use a neat number theory trick to solve this one. It's a known fact amongst mathematicians that the sum of all the natural numbers up to a certain N (where N is finite) can be calculated by the following expression:

By knowing this property of the natural numbers a simple solution emerges. Since we know there is only one number missing in the permutation [1, N] then we can subtract the sum of the input from the sum of all the natural numbers up to N, by doing this every number will cancel out except one, the missing number.

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

int main() {
    long long int n, input, sum = 0;
    cin >> n;

    for (int i = 0 ; i < n - 1 ; i++) {
        cin >> input;
        sum += input;
    }

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

    return 0;
}