Grade 9 · Frequency arrays, prefix sums and the Sieve of EratosthenesCitește în română

The missing number in a permutation

Original: Numărul lipsă dintr-o permutare

O(n)C++1733 lines1 example

The idea

n and n - 1 distinct numbers from the set {1, 2, ..., n} are given; exactly one is missing. The sum of all numbers from 1 to n is n · (n + 1) / 2 (Gauss's formula), so the missing number is the difference between this sum and the sum of the numbers read. Neither an array nor sorting is needed.

Original description (Romanian)

Se dau n și n - 1 numere distincte din mulțimea {1, 2, ..., n}; unul singur lipsește. Suma tuturor numerelor de la 1 la n este n · (n + 1) / 2 (formula lui Gauss), așa că numărul lipsă este diferența dintre această sumă și suma numerelor citite. Nu e nevoie nici de vector, nici de sortare.

Complexity
O(n)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

5
3 1 5 2

Expected output

4

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

numarul-lipsa.cpp
/*
 * Titlu: Numărul lipsă dintr-o permutare
 * Clasa: 9
 * Capitol: Frecvență, sume parțiale și ciurul lui Eratostene
 * Descriere: Se dau n și n - 1 numere distincte din mulțimea {1, 2, ..., n};
 *            unul singur lipsește. Suma tuturor numerelor de la 1 la n este
 *            n · (n + 1) / 2 (formula lui Gauss), așa că numărul lipsă este
 *            diferența dintre această sumă și suma numerelor citite. Nu e nevoie
 *            nici de vector, nici de sortare.
 * Complexitate: O(n)
 *
 * Exemplu
 * Intrare:
 * 5
 * 3 1 5 2
 * Ieșire: 4
 */
#include <iostream>
using namespace std;

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

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.