Numere25

Se dă un număr natural n și un șir de numere naturale din intervalul [1,n] ordonate crescător. Să se afișeze în ordine strict crescătoare toate numerele din intervalul [1,n] care nu se găsesc în șirul dat. Dacă nu există asemenea numere se afișează Nu exista.

Date de intrare

Fișierul de intrare numere25.in conține pe prima linie numărul n, iar pe a doua linie șir de numere naturale din intervalul [1,n] ordonate crescător.

Date de ieșire

Fișierul de ieșire numere25.out va conține pe prima linie în ordine strict crescătoare toate numerele din intervalul [1,n] care nu se găsesc în șirul dat. Dacă nu există asemenea numere fișierul va conține textul Nu exista.

Restricții și precizări

  • 1 ≤ n ≤ 107;
  • în enunțul original, 1 ≤ n ≤ 109; aici limitele au fost micșorate, datorită dimensiunilor prea mari ale fișierelor de intrare/ieșire;
  • proiectați un algoritm eficient din punctul de vedere al memoriei şi al timpului de executare:
    • se recomandă evitarea utilizării tablourilor sau a altor structuri de date similare.

Exemplu

numere25.in

10
3 4 4 8

numere25.out

1 2 5 6 7 9 10
#include <fstream>

using namespace std;
ifstream cin("numere25.in");
ofstream cout("numere25.out");

int main()
{
    int n,y,x=0,ok=0;
    cin>>n;
    while(cin>>y)
    {
       for(int i=x+1;i<y;i++)
           {
            cout<<i<<" ";
            ok=1;
        }
        x=y;
    }
    for(int i=y+1;i<=n;i++)
        cout<<i<<" ",ok=1;

    if(ok==0)
        cout<<"Nu exista";
    return  0;
}
%d bloggers like this: