Probleme cu numere lipsa si nu numai ...

(Categoria Diverse, autor Cosmin Negruseri)

• Cuprins
• Problema 1 ( interviu Microsoft )
• Problema 2 ( interviu Microsoft )
• Problema 3 ( interviu Microsoft, lot 1999 )
• Problema 4 ( IBM Research: Ponder This )
• Problema 5
• Problema 6 (interviu Microsoft
• Problema 7 (interviu Microsoft
• Problema 8 (interviu Microsoft

Problema 1 ( interviu Microsoft )

Se dau n-1 numere distincte de la 1 la n, sa se dea un algoritm cat mai eficient care sa determine numarul lipsa.

Rezolvare

Prima rezolvare ce ne poate veni in minte este aceea de a verifica daca fiecare numar 1 -> n este prezent in sirul nostru, printr-o parcurgere (acest algoritm are complexitatea O(n²) ). O alta rezolvare triviala ar fi sa sortam numerele si sa determinam prin parcurgere numarul i pentru care a[i] != i (pentru sortari rapide algoritmul are complexitatea O(n log n) ).

O rezolvare mai eficienta poate fi data folosind Divide et Impera. Putem imparti numerele in doua multimi, una in care vom pune mumerele mai mici sau egale cu n/2, iar in cealalta restul. Acum vom sti din care din cele doua multimi lipseste numarul, dupa numarul de elemente al acestora. Considerand T(n) timpul de executie al algoritmului, atunci complexitatea devine T(n) = T(n/2) + O(n) = O(n). Deci algoritmul este liniar, si foloseste memorie O(n), ignorand memoria consumata de stiva din algoritmul Divide et Impera ( O(log n) ). O alta idee este de a folosi un tabel de dispersie sau un sir de valori booleene care va folosi memorie suplimentara O(n) (poate fi redusa la O(n/log n) daca se lucreaza pe biti).

O rezolvare eleganta se foloseste de proprietatea ca suma numerelor naturale de la 1 la n este n(n + 1)/2. Numarul lipsa este egal cu diferenta dintre n(n + 1 )/2 si suma numerelor noastre. Aceasta solutie are complexitatea O(n) (parcurgem sirul pentru a determina suma) ca timp si O(1) ca memorie. Daca n este destul de mare, s-ar putea ca n(n+1)/2 sa depaseasca domeniul de reprezentare al intregilor, rezultand in necesitatea implementarii operatiilor cu numere mari. Pentru a evita acest lucru folosim operatia xor (notata prin ^∧ ) si proprietatile ei a ^∧ a = 0 si a ^∧ b = b ^∧ a. Vom face suma xor a numerelor a[i] ^∧ i (1 <= i <= n):
S = a[ 1 ] ^∧ 1 ^∧ a[ 2 ] ^∧ 2 ^∧ ... ^∧ a[ n - 1 ] ^∧ n - 1 ^∧ n

Astfel fiecare numar care apare in sir va fi in suma de doua ori si va fi anulat, iar rezultatul final va fi indicele numarului lipsa. Solutia are compexitatea O(n) ca timp si O(1) ca spatiu.

Problema 2 ( interviu Microsoft )

Se da un sir de n+1 numere de la 1 la n in care unul se repeta, iar restul sunt distincte. Sa se dea un algoritm cat mai eficient care sa determine numarul ce se repeta.

Rezolvare

Evident, abordarile de la problema anterioara se aplica si aici.

Problema 3 ( lot 1999, interviu Microsoft )

Se da o lista inlantuita prin primul ei element. Se cere un algoritm cat mai eficient care sa determine daca lista are sau nu ciclu.

Rezolvare

Fie n numarul total de elemente ale listei. O solutie triviala in O(n) timp si O(n) memorie ar fi sa parcurgem lista si sa adaugam pe rand elementele unui tabel de dispersie (cand apare de doua ori acelasi element rezulta ca am gasit un ciclu). O metoda folosita de unii concurenti este parcurgerea listei pe o perioada de timp determinata (timpul de executie fixat), fiind sanse mari ca un ciclu sa nu existe daca nu s-a gasit nici unul pana la momentul incheierii executiei.

Exista un algoritm mai elegant, care ruleaza tot in timp liniar. El se numeste Algoritmul lui Floyd de detectie a ciclului intr-o lista. O aplicatie importanta este Algoritmul Pollard ρ, folosit pentru factorizarea intregilor cu multe cifre. Se folosesc doi pointeri a si b, unde a se misca de doua ori mai repede decat b in lista (denumit si Algoritmul iepurelui si testoasei). Reprezentarea grafica seamana cu litera greceasca ρ. Notam lungimea lantului cu λ si lungimea ciclului cu μ.

//cap - pointer spre capatul listei
a = b = cap;
do{
    b = a -> next;
    a = a -> next -> next;
}while(a != b);

Cand a si b sunt amandoi in ciclu, este evident ca la un moment dat a = b. In exemplul desenat, dupa sase iteratii cei doi pointeri vor indica acelasi element. Pentru determinarea lungimii ciclului se mai poate face o parcurgere in care doar un pointer se misca. Acum dupa ce stim lungimea μ a ciclului, putem afla si lungimea λ a lantului astfel: luam un pointer la inceputul listei si al doilea care a facut deja μ pasi in lista (amandoi pointerii au aceeasi viteza). Dupa λ pasi ei vor fi egali. Astfel am obtinut o rezolvare liniara.

Problema 4 ( IBM Research: Ponder This )

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.

Rezolvare

Aici nu merge solutia cu suma xor de la problemele 1 si 2 pentru ca numerele pot fi repetate oricum si nu putem folosi relatiile obtinute pentru a determina un numar care se repeta. Daca toate elementele din sir ar fi distincte, atunci sirul ar avea structura unei permutari. Cum ele nu sunt neaparat distincte ne vine ideea de a vedea care este diferenta intre un asemenea sir si o permutare, pentru a folosi idei care apar la permutari (ciclurile acestora). Fiecare element din sirul nostru indica inspre altul, deci il putem considera un graf orientat in care arcele sunt (i, a[i]). De exemplu putem face urmatoarea reprezentare pentru sirul 3, 2, 1, 3, 4:

Din fiecare nod iese cate un arc si cum sunt un numar finit de noduri rezulta ca din orice nod pornim ajungem intr-un ciclu. Chiar in momentul in care intram in ciclu, acel numar se va repeta, deci vrem ca la inceput sa fim intr-un nod ce nu apartine vreunui ciclu. Spre fericirea noastra un astfel de nod e nodul n, pentru ca nici un element a[i] nu va fi egal cu n. Deci daca pornim de la nodul n suntem in afara vreunui ciclu si putem sa mergem pe drumul pe care il indica pentru a ajunge eventual intr-un ciclu. Am vazut in problema anterioara cum determinam pentru o lista ce are ciclu lungimea lantului, astfel putem determina elementul de la intrarea in ciclu in complexitate O(n) si problema noastra este rezolvata.

Problema 5

Se da un sir de N intregi ce contine numere intre 1 si N. Sa se determine daca acest numar este o permutare cat mai eficient, fara a distruge sirul.

Rezolvare

Pentru ca valorile sirului sunt intregi iar valorile elementelor unei permutari sunt pozitive rezulta ca ne putem folosi de bitul de semn al fiecarui numar pentru ca acesta ramane liber. Vom verifica intai daca exista vreun element negativ in sir. Apoi daca nu exista vom marca elementele parcurse din ciclurile permutarii astfel a[i] = -a[i]. Daca trebuie sa marcam un element de doua ori sau in parcurgerea initiala am gasit un numar negativ atunci cele N numere nu reprezinta o permutare. Pentru a aduce sirul inapoi la starea initiala vom schimba toate elementele ce au semn negativ din sir cu valorile lor in modul. Astfel am obtinut o rezolvare liniara ce foloseste spatiu suplimentar O(1).