Missing Number Solution - [CSES]

~ 2 min read

By Daniel Diaz

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

Problem statement

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

2≤n≤2∗1052 \le n \le 2 * 10^{5}

Original problem statement.

Example test case

Input:

2 1 4 5

Output:

3

Explanation

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

Solution

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.

∑i=1ni=n(n+1)2\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.

n(n+1)2−sum\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 231−12^{31} - 1 , the maximum number an integer can hold.

Share:
Read Next 📖