Am mai multe probleme si as avea nevoie de niste idei deoarece trebuie sa fie cat mai optimi algoritmii.
O problema ar suna cam asa:
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.
Fie n numarul maxim (in cazul tau 1.000.000.000)
Fie s suma numerelor din fisier.
Stiind ca 1+2+…n = n * (n + 1)/2, atunci numarul lipsa va fi:
n * (n + 1)/2 – s
Foloseste variabile de tip unsigned long long in care sa tii sumele.
mersi
ar mai fi o metoda cu xor (sau exclusiv). insa nu stiu care ar fi ce-a mai eficienta dintre astea pentru 1 000 000 000.
pentru numere si mai mari asta cu suma nu s-ar mai putea folosi.
Rezolvarea cu xor e geniala. Din punct de vedere al memoriei folosite si a timpului de executie cred ca e O. Problema din cate stiu eu e facuta sa intre si solutia in O(n) asha ca nu te mai agita degeaba ca n-o gasesti pe aia cu xor.