h3. Rezolvare

Acum vom folosi din nou un algoritm bazat pe Divide et Impera. La primul pas impartim multimea in doua submultimi - cea a numerelor pare si cea a numerelor impare, si vedem in care din ele se gaseste numarul nostru lipsa (am aflat astfel ultimul bit al rezultatului). Acum putem aplica recursiv procedura aceasta pe numerele din o lista cu jumatate din lungimea listei initiale impartite la doi (ignoram ultimul bit al numerelor). Aceasta solutie are complexitate $O(n)$ pentru ca dupa fiecare pas executat in timp liniar, dim

Acum vom folosi din nou un algoritm bazat pe Divide et Impera. La primul pas impartim multimea in doua submultimi - cea a numerelor pare si cea a numerelor impare, si vedem in care din ele se gaseste numarul nostru lipsa (am aflat astfel ultimul bit al rezultatului). Acum putem aplica recursiv procedura aceasta pe numerele din o lista cu jumatate din lungimea listei initiale impartite la doi (ignoram ultimul bit al numerelor). Aceasta solutie are complexitate $O(n)$ pentru ca dupa fiecare pas executat in timp liniar, dimensiunea problemei se injumatateste. Memoria suplimentara e $O(n)$ (doi vectori care sa pastreze indicii elementelor pare, respectiv impare).
 
h2(#prob9). Problema 9
 
Generalizam problema anterioara si se cere un algoritm eficient pentru un sir din care lipsesc $n - k$ numere.
 
h3. Rezolvare
 
Din nou vedem cate numere din sir au ultima cifra $0$ si cate au $1$. Astfel putem determina $k{~0~}$ - numarul de valori lipsa cu ultima cifra $0$, si $k{~1~}$ - numarul de valori lipsa care au ultima cifra $1$. Daca notam timpul de rezolvare al problemei noastre $T(n, k)$, acum avem de rezolvat doua subprobleme cu timpii $T(n/2, k{~0~})$ si $T(n/2, k{~1~})$. Acum impartim cele $k{~0~}$ numere in $k{~00~}$ si $k{~10~}$ valori care se termina in $00$, respectiv $10$ in reprezentarea in baza $2$. Aceasta solutie are complexitate $O(n log n)$ si nu imbunatateste cu nimic solutia in care sortam elementele sirului.
 
h2(#prob10). Problema 10 ( _el judge_ )
 
Se dau $n$ numere intregi astfel incat fiecare numar apare de un numar par de ori, in afara de unul singur, care apare de un numar impar de ori. Se cere determinarea acelui numar. De exemplu in sirul $1 2 2 3 1 2 2 2 3 3 3$, numai elementul $2$ apare de un numar impar de ori.
 
h3. Rezolvare
 
Este evident ca daca facem suma xor a tuturor numerelor, rezultatul va fi numarul ce apare de numar impar de ori. Astfel solutia are complexitatea $O(n)$ ca timp si $O(1)$ ca memorie folosita.
 
h2(#prob11). Problema 11 ( _Info-Oltenia 2005, clasa a IX-a_ )
 
Se dau $n$ siruri formate din cifre de la $1$ la $8$ (inclusiv), de lungime maxima $500$. Toate sirurile sunt repetate de $k$ ori sau de multiplu de $k$ ori, cu exceptia unui singur sir, care nu este repetat de $k$ ori, sau de multiplu de $k$ ori. Sa se afiseze sirul care nu se repeta. ( $1 <= n <= 32000, k < 2005$ )
 
h3. Rezolvare
 
Putem face o solutie similara cu cea de mai sus. Consideram un tablou $A$ cu $500 * 8$ elemente, fiecare linie $i$ corespunzand cifrelor de pe pozitia $i$ din sirurile de cifre date la intrare. Cand procesam un sir dintre cele date la intrare, daca el are pe pozitia $i$ cifra $j$ atunci incrementam elementul $A[ i ][ j ]$. In acest tablou, pe fiecare linie $i$, toate elementele in afara de unul vor fi $0$ sau multiplu de $k$, iar elementul $A[ i ][ j ]$ care nu e multiplu de $k$ este a $j$-a cifra a numarului care se repeta de un numar de ori ce nu este divizibil cu $k$. Aceasta solutie are complexitate ca timp $O(n*L)$, iar ca spatiu $O(L)$, unde $L$ este lungimea maxima a unui sir de cifre.
 
h2(#biblio). Bibliografie
 
*(#fn1) 1. http://mathworld.wolfram.com/VietasFormulas.html
*(#fn2) 2. http://mathworld.wolfram.com/Newton-GirardFormulas.html
*(#fn3) 3. http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm