Problema fisier - optimizare

[•XamWaZ]

Se da un fisier care contine 999.999.999 de numere intregi distincte intre 1 si 1.000.000.000 (toate numerele in afara de unul vor fi in fisier). Sa se gaseasca acest numar lipsa. Gasiti o metoda optima din punct de vedere al timpului, dar si al memoriei consumate.

Mie nu imi vine nicio idee:(

[•PlayLikeNeverB4]

Daca n-ar lipsi niciunul care ar fi suma elementelor?

[•XamWaZ]

Daca n-ar lipsi niciunul care ar fi suma elementelor?

nu stiu, se face cu formula: n(n+1)/2, dar ce conteaza asta?
crezi ca ar fi mai eficient sa faci suma celor din fisier si in functie de aia sa iti dai seama care lipseste?
ar veni un numar cam de maxim 19 cifre suma aia.

[•pauldb]

Suma ar intra pe long long fara probleme.

Nu ai cum sa-ti dai seama ce numar lipseste fara macar sa parcurgi numerele.

[•Cosmin]

http://infoarena.ro/missing-numbers