Grade 12 · Baccalaureate exam reviewCitește în română

File: the values that appear exactly once

Original: Fișier — valorile care apar o singură dată

O(n)C++1747 lines2 examplesuses date.in / date.out

The idea

The task (exam part III.3 style): the file date.in holds at most 10^6 natural numbers with at most three digits, separated by spaces. Print on the screen, in increasing order, the values that appear exactly once in the file, or 'nu exista' (none). Efficiency: we neither store nor sort the sequence. Since the values are between 0 and 999, a frequency array f[1000] counts the occurrences while reading (O(1) per number), then walking the array from 0 to 999 gives the increasing order directly. The memory used does not depend on how many numbers the file holds.

Original description (Romanian)

Cerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 numere naturale de cel mult trei cifre, separate prin spații. Afișați pe ecran, în ordine crescătoare, valorile care apar exact o dată în fișier, sau „nu exista”. Eficiența: nu memorăm șirul și nu îl sortăm. Cum valorile sunt între 0 și 999, un vector de frecvență f[1000] numără aparițiile la citire (O(1) pe număr), apoi parcurgerea vectorului de la 0 la 999 dă direct ordinea crescătoare. Memoria folosită nu depinde de câte numere sunt în fișier.

Complexity
O(n + 1000) timp, O(1000) memorie
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input (date.in)

5 12 7 5 300 12 999 0 0

Expected output

7 300 999
Example 2

Input (date.in)

4 4 4

Expected output

nu exista

The code

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

fisier-valori-unice.cpp
/*
 * Titlu: Fișier — valorile care apar o singură dată
 * Clasa: 12
 * Capitol: Recapitulare pentru bacalaureat
 * Descriere: Cerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6
 *            numere naturale de cel mult trei cifre, separate prin spații. Afișați
 *            pe ecran, în ordine crescătoare, valorile care apar exact o dată în
 *            fișier, sau „nu exista”. Eficiența: nu memorăm șirul și nu îl sortăm.
 *            Cum valorile sunt între 0 și 999, un vector de frecvență f[1000]
 *            numără aparițiile la citire (O(1) pe număr), apoi parcurgerea
 *            vectorului de la 0 la 999 dă direct ordinea crescătoare. Memoria
 *            folosită nu depinde de câte numere sunt în fișier.
 * Complexitate: O(n + 1000) timp, O(1000) memorie
 *
 * Exemplu
 * Intrare: 5 12 7 5 300 12 999 0 0
 * Ieșire: 7 300 999
 *
 * Exemplu
 * Intrare: 4 4 4
 * Ieșire: nu exista
 */
#include <fstream>
#include <iostream>
using namespace std;

int f[1000];

int main()
{
    ifstream fin("date.in");
    int x;
    while (fin >> x)
        f[x]++;
    bool gasit = false;
    for (int v = 0; v < 1000; v++)
        if (f[v] == 1)
        {
            cout << v << ' ';
            gasit = true;
        }
    if (!gasit)
        cout << "nu exista";
    cout << '\n';
    return 0;
}

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