Problema saptamanii - Duplicate

Cosmin Negruseri
14 august 2010

Continuam cu alta problema ceva mai simpla.

Se da un stream pe care il putem citi de un numar constant de ori. El contine n + 1 numere intregi de la 1 la n. Evident vor exista duplicate in stream. Se cere sa se gaseasca un algoritm care parcurge streamul de un numar constant de ori, foloseste memorie mai mica decat O(n) biti si gaseste un element duplicat in stream. Un stream are metodele bool hasNext() si int getNext(), si e o abstractizare a unui set de date ce poate fi citit secvential.

Puteti trimite solutiile pe adresa cosminn at gmail.com