Clasa a IX-a · Frecvență, sume parțiale și ciurul lui EratosteneRead in English

Numărul lipsă dintr-o permutare în C++

În engleză: The missing number in a permutation

O(n)C++1733 de linii1 exemplu

Ideea

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.

Descrierea în engleză

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.

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

Exemple

Exemplul 1

Intrare

5
3 1 5 2

Ieșire așteptată

4

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

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;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.