Problema saptamanii Duplicate - Solutie

Cosmin Negruseri
20 august 2010

Problema duplicate a fost abordabila, fiind rezolvata de 16 cititori. Am aflat-o de la Mihai Patrascu.

Rezolvitori:
Dumitru Daniliuc, Andrei Grigorean, Tiberiu Savin, Andrei Dragus, Alex Mosoi, Marius Pungaru, Adrian Vladu, Marius Andrei, Daniel Dumitran, Marius Dragus, Andrei Marius Teodorescu, Laura Draghici, Delia David, Adrian Airinei, Armand Rotaru si Stefan Istrate.

Solutie:
Fie x = [sqrt n]. Timem un sir de x pozitii F[i] cu frecventele elementelor pe intervalul [i * x + 1, (i + 1) * x]. Din principiul lui Dirichet rezulta ca un interval va avea mai mult de x elemente in el. Prin o parcurgere al sirului aflam un astfel de interval. Cu o a doua parcurgere aflam frecventele exacte ale elementelor din intervalul respectiv folosind un sir de dimensiune x. Am determinat astfel un element duplicat folosind doua parcurgeri si memorie O(sqrt(n) log n) biti.

Probleme inrudite:

Pentru probleme pe acelasi stil cu nivel de dificultate bun pentru interviuri tehnice pentru programatori puteti citi articolul Probleme cu numere lipsa si nu numai. Doua exemple:

1. Un sir de lungime n contine numere intregi din multimea {1, 2, ..., n-1}. Folosind Principiul lui Dirichlet deducem ca cel putin un element se repeta. Gasiti un algoritm liniar care afiseaza o valoare ce se repeta, folosind memorie suplimentara constanta si nemodificand la nici un pas vreun element din sir.

2. Se dau n numere de la 1 la n. Unul din ele unul apare de doua ori in sir, iar restul sunt distincte. Evident ca un numar nu va aparea niciodata. Sa se dea un algoritm cat mai eficient care sa determine numarul lipsa si numarul ce apare de doua ori.