# Missing Number Solution - [CSES]

/* Let's solve the introductory problem, missing number, from the CSES problem set. */

You are given all numbers from 1 to n. Except for one missing number. Your task is to output that missing number.

$2 \le n \le 2 * 10^{5}$

Input:

2 1 4 5

Output:

3

In the input, you’re given the numbers 1 2 4 5, which means the only missing number is 3.

You can get the missing number, in two ways.

Since n is relatively small, we can create a boolean array, and mark all the existing numbers in the input.

This way, if we iterate from 1 to n inside the array we’ll find the missing number if it’s not marked.

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
bool a[MAX];

int main(){
int n; cin >> n;
for (int i =0; i < n - 1; i++){
int x; cin >> x;
// Mark number
a[x] = true;
}
for (int i = 1; i <= n; i++){
if (!a[i]){
cout << i << endl;
break;
}
}
}

We can also use a little bit of math. We know how to get the sum of the numbers from 1 to n.

$\displaystyle \sum_{i = 1}^{n} i = \frac{n (n + 1)}{2}$

So if we know n, and the sum of all the numbers from 1 to n, except for the missing one, we can obtain the latter by doing.

$\frac{n (n + 1)}{2} - sum$

In C++, we could write.

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;

int main(){
long long n, sum = 0; cin >> n;
for (int i =0; i < n - 1; i++){
long long x; cin >> x;
sum += x;
}
cout << (n * (n + 1)) / 2 - sum << endl;
}

We need to use long long because in some cases, the summation of 1 to n exceeds $2^{31} - 1$ , the maximum number an integer can hold.

Share: