h1. Probleme cu numere lipsa si nu numai ...
h1. Probleme cu numere lipsa si nu numai...
(Categoria _Diverse_, autor _Cosmin Negruseri_)
== include(page="template/implica-te/scrie-articole" user_id="alecman") ==
h2. Problema 1 ( _interviu Microsoft_ )
(Categoria _Algoritmi_, Autor _Cosmin Negruseri_)
Se dau <tex>n-1</tex> numere distincte de la <tex>1</tex> la <tex>n</tex>, sa se dea un algoritm cat mai eficient care sa determine numarul lipsa.
(toc){width: 25em}*{text-align:center} *Cuprins*
* 'Problema 1 ( _interviu Microsoft_ ) ':missing-numbers#prob1
* 'Problema 2 ( _interviu Microsoft_ ) ':missing-numbers#prob2
* 'Problema 3 ( _interviu Microsoft, lot 1999_ ) ':missing-numbers#prob3
* 'Problema 4 ( _IBM Research: Ponder This_ ) ':missing-numbers#prob4
* 'Problema 5 ':missing-numbers#prob5
* 'Problema 6 ( _interviu Microsoft_ ) ':missing-numbers#prob6
* 'Problema 7 ':missing-numbers#prob7
* 'Problema 8 ':missing-numbers#prob8
* 'Problema 9 ':missing-numbers#prob9
* 'Problema 10 ( _el judge_) ':missing-numbers#prob10
* 'Problema 11 ( _Info-Oltenia 2005, clasa a IX-a_) ':missing-numbers#prob11
* 'Problema 12 ( _JBOI 2011 Bistrita_) ':missing-numbers#prob12
* 'Bibliografie':missing-numbers#biblio
h3. Rezolvare
Prima rezolvare ce ne poate veni in minte este aceea ca pentru fiecare numar de la <tex>1</tex> la <tex>n</tex> sa verificam daca numarul curent nu exista in sir prin o parcurgere. Un astfel de algoritm are complexitatea <tex>O(n^{2})</tex> si vom vedea mai departe ca putem obtine solutii mult mai bune.
h2(#prob1). Problema 1 ( _interviu Microsoft_ )
O rezolvare triviala ar fi sa sortam cu metoda noastra preferata numerele si sa le parcurgem pentru a vedea cand <tex>a[i] != i</tex>. Aceasta rezolvare are complexitatea <tex>O(n \log n)</tex>.
Se dau $n-1$ numere distincte de la $1$ la $n$, sa se dea un algoritm cat mai eficient care sa determine numarul lipsa.
O rezolvare mai eficienta poate fi data urmarind ideea algoritmului **Quick Sort**. Putem imparti numerele in doua multimi, una in care vom pune mumerele mai mici sau egale cu <tex>n/2</tex>, iar in cealalta numerele mai mari decat <tex>n/2</tex>. Acum vom sti daca numarul lipsa este mai mic sau egal cu <tex>n/2</tex> sau mai mare ca <tex>n/2</tex>, dupa numarul de elemente din fiecare lista. Astfel in <tex>O(n)</tex> pasi am redus problema la jumatate. Daca avem <tex>T(n)</tex> timpul de executie al acestui algoritm, atunci <tex>T(n) = T(n/2) + O(n) = O(n)</tex>. Deci algoritmul este liniar, si foloseste memorie <tex>O(n)</tex> ignorand memoria consumata de sirul de numere <tex>O(\log n)</tex> pentru stiva din algoritmul _divide et impera_.
O alta idee este aceea de a folosi un tabel de dispersie sau un sir de valori _booleene_ care va folosi memorie suplimentara <tex>O(n)</tex>, iar daca folosim biti reducem memoria suplimentara la <tex>O(n/\log n})</tex>.
h3. Rezolvare
O rezolvare eleganta se foloseste de proprietatea ca suma numerelor naturale de la <tex>1</tex> la <tex>n</tex> este <tex>n(n+1)/2</tex>, iar suma numerelor o putem afla prin o parcurgere. Acum determinarea numarului lipsa se face prin scaderea din suma numerelor de la <tex>1</tex> la <tex>n</tex> a sumei numerelor noastre. Aceasta solutie are complexitatea <tex>O(n)</tex> ca timp si <tex>O(1)</tex> ca memorie folosita.
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^2^)$ ). 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)$ ).
Daca <tex>n</tex> este destul de mare, s-ar putea ca <tex>n(n+1)/2</tex> sa depaseasca domeniul de reprezentare al intregilor de pe calculatorul nostru si ar trebui sa implementam operatii cu numere mari ca solutia anterioara sa produca rezultatul corect. O rezolvare ce nu are aceasta problema se foloseste de operatia **xor** si de proprietatile ei <tex>a \hspace{1mm} xor \hspace{1mm} a = 0</tex> si <tex>a \hspace{1mm} xor \hspace{1mm} b = b \hspace{1mm} xor \hspace{1mm} a</tex>. Vom face suma _xor_ a numerelor <tex>a[i] \hspace{1mm} xor \hspace{1mm} i</tex> cu <tex>i</tex> de la <tex>1</tex> la <tex>n</tex>:
O rezolvare mai eficienta poate fi data folosind _Divide et Impera_. Putem imparti numerele in doua multimi, una in care vom pune numerele 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).
<tex>S = a[1] \hspace{1mm} xor \hspace{1mm} 1 \hspace{1mm} xor \hspace{1mm} a[2] \hspace{1mm} xor \hspace{1mm} 2 \hspace{1mm} xor \hspace{1mm} ... \hspace{1mm} xor \hspace{1mm} a[n] \hspace{1mm} xor \hspace{1mm} n</tex>
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 pentru numarul lipsa, in suma va aparea doar indicele lui, care este si valoarea finala a sumei. Solutia are compexitatea <tex>O(n)</tex> ca timp si <tex>O(1)</tex> ca spatiu.
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.
h2. Problema 2 ( _interviu Microsoft_ )
h2(#prob2). Problema 2 ( _interviu Microsoft_ )
Se da un sir de <tex>n+1</tex> numere de la <tex>1</tex> la <tex>n</tex> in care unul se repeta, iar restul sunt distincte. Sa se dea un algoritm cat mai eficient care sa determine numarul ce se repeta.
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.
h3. Rezolvare
Evident, abordarile de la problema anterioara se aplica si aici.
h2. Problema 3 ( lot 1999, _interviu Microsoft_ )
h2(#prob3). 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.
h3. Rezolvare
Fie <tex>n</tex> numarul total de elemente ale listei. O solutie in <tex>O(n)</tex> timp si <tex>O(n)</tex> memorie ar fi sa parcurgem lista si sa adaugam pe rand elementele listei unui tabel de dispersie. Cand am introdus acelasi element de doua ori in lista este evident ca am gasit un ciclu. O metoda folosita de unii concurenti a fost parcurgerea listei pe o perioada de timp determinata, de exemplu timpul de executie fixat in problema. Acum sunt sanse mari ca daca nu am ajuns la capatul listei aceasta sa aiba ciclu.
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 ce foloseste memorie suplimentara <tex>O(1)</tex> si este liniar. Acest algoritm se numeste _Algoritmul lui Floyd de detectie a ciclului intr-o lista_. O aplicatie importanta a lui este _Algoritmul Pollard_ <tex>\rho</tex>, folosit pentru factorizarea intregilor cu multe cifre. Algoritmul foloseste doi pointeri <tex>a</tex> si <tex>b</tex>, unde <tex>a</tex> se misca de doua ori mai repede decat <tex>b</tex> in lista, de aceea se mai numeste si _Algoritmul iepurelui si testoasei_.
Reprezentarea grafica seamana cu litera greceasca <tex>\rho</tex>. Notam lungimea lantului cu <tex>\lambda</tex> si lungimea ciclului cu <tex>\mu</tex>.
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 μ.
!missing-numbers?missing_numbers_pic2.png!
== code(c) |
a = b = cap
repeta
a = a.next.next
b = a.next
cat timp (a!=b)
//cap - pointer spre capatul listei
a = b = cap;
do{
b = b -> next;
a = a -> next -> next;
}while(a != b);
==
Cand <tex>a</tex> si <tex>b</tex> sunt amandoi in ciclu, <tex>a</tex> il va ajunge din nou pe <tex>b</tex>. Puteti vedea exact cum prin analiza cazurilor in care lungimea ciclului e para sau impara. 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 <tex>\mu</tex> a ciclului putem afla si lungimea <tex>\lambda</tex> a lantului astfel: luam un pointer la inceputul listei si al doilea care a facut deja <tex>\mu</tex> pasi in lista. Acum ii miscam pe cei doi cu aceeasi viteza. Dupa <tex>\lambda</tex> pasi cei doi pointeri vor fi egali. Astfel am obtinut o rezolvare liniara.
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.
h2(#prob4). 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.
h3. 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$:
!missing-numbers?missing_numbers_pic3.png!
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. In momentul in care intram in ciclu, acel numar se va repeta, deci vrem ca primul nod sa nu apartina nici unui ciclu. 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 oricarui 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 lungimea lantului pentru o lista ce contine un ciclu. Putem determina astfel elementul de la intrarea in ciclu in complexitate $O(n)$ si problema noastra este rezolvata.
h2(#prob5). Problema 5
Se da un sir de $N$ intregi ce contine numere intre $1$ si $N$. Sa se determine cat mai eficient daca acest numar este o permutare, fara a distruge sirul.
h3. Rezolvare
Pentru ca valorile sirului sunt intregi, iar valorile elementelor unei permutari sunt pozitive, rezulta ca putem folosi bitul de semn al fiecarui numar pentru ca acesta ramane liber. Verificam mai 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 un element este marcat de doua ori sau am gasit initial un numar negativ, atunci cele $N$ numere nu reprezinta o permutare. Pentru a reface sirul initial, 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)$.
h2(#prob6). Problema 6 ( _interviu Microsoft_ )
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.
h3. Rezolvare
Notam cu $a$ numarul lipsa si cu $b$ numarul ce apare de doua ori. Majoritatea celor care stiu sa rezolve problema $1$ prin cele doua solutii optime (suma numerelor si suma xor) incearca sa rezolve aceasta problema determinand doua relatii diferite asupra lui $a$ si $b$, din care apoi incearca sa obtina valorile cerute. Scazand din $n(n + 1)/2$ suma numerelor din fisier obtinem valoarea pentru $a - b$, iar facand suma xor a numerelor din fisier si a numerelor de la $1$ la $n$ obtinem valoarea pentru $a ^∧^ b$. In acest moment putem considera ca problema este rezolvata, dar la o analiza mai atenta se poate observa ca numerele care verifica relatiile respective nu sunt unice. De exemplu pentru $a = 10$ si $b = 9$ obtinem valorile $a - b = 1$ si $a ^∧^ b = 3$. Aceleasi valori le obtinem si pentru $a = 6$ si $b = 5$. Se observa de aici ca cele doua relatii nu pot fi folosite pentru a rezolva problema.
Stim care este valoarea diferentei $D{~1~} = a - b$, dar mai avem nevoie de o relatie pentru a determina numerele $a$ si $b$. Vom incerca in continuare sa folosim operatia de inmultire pentru a obtine cea de-a doua relatie. Vom avea: $a/b = n! / (a[ 1 ] * a[ 2 ] * ... * a[ n ])$. Aceasta relatie nu poate fi calculata in $O(n)$ pentru ca numarul de cifre al lui $n!$ nu este constant. Pentru a evita lucrul cu numere mari am putea sa logaritmam intreaga relatie, obtinand $lg a - lg b = lg 1 + lg 2 + ... + lg n - lg a[ 1 ] - lg a[ 2 ] - ... - lg a[ n ]$. Aceasta rezolvare ar fi buna daca ar fi posibila realizarea unor calcule perfecte cu numere reale. Din pacate acest lucru nu este posibil si rezolvarea are mari probleme cu precizia.
O a doua relatie o putem obtine ca diferenta intre suma patratelor numerelor de la $1$ la $n$ si suma patratelor numerelor din fisier. Obtinem astfel $D{~2~} = a^2^ - b^2^$. Din aceste doua relatii putem usor afla ca $a = (D{~1~} + D{~2~}/D{~1~})/2$ si $b = (D{~2~}/D{~1~} - D{~1~})/2$. Aceasta rezolvare are complexitatea $O(n)$ ca timp si $O(1)$ ca spatiu.
h2(#prob7). Problema 7
Se dau $n - k$ numere distincte de la $1$ la $n$. Sa se dea un algoritm cat mai eficient care sa determine numerele lipsa.
h3. Rezolvare
Fie $a, b, c, ...$ numerele ce lipsesc. Am putea extinde ideea din problema anterioara pentru a obtine in $O(n*k)$ sumele $S{~1~} = a + b + c + ..., S{~2~} = a^2^ + b^2^ + c^2^ + ..., ..., S{~k~} = a^k^ + b^k^ + c^k^ + ...$ si sa obtinem valorile elementelor $a, b, c, ...$, dar in general daca valoarea lui $k$ este variabila, atunci putem gasi solutia ce satisface toate cele $k$ relatii in timp exponential. O metoda este de a transforma relatiile intr-un polinom de radacini $a, b, c, ...$. Pentru a gasi $P(x) = a{~0~}X^k^ + a{~1~}X^k-1^ + ... + a{~k~}$ putem folosi relatiile lui Viete[1]
$s{~1~} = a + b + c + d + ...$
$s{~2~} = ab + ac + ad + bc + bd + cd + ...$
$s{~3~} = abc + acd + bcd + ...$
$s{~4~} = abcd + ...$
...
$s{~i~} = (-1)^i^ a{~n-i~}/a{~n~}$
Aceste sume $s{~k~}$ sunt numite polinoame simetrice si sunt strans legate de sumele de puteri $k S{~k~}$ prin relatiile Newton Girard[2]. Astfel avem un algoritm ce determina polinomul in $O(nk)$ si spatiu $O(k)$ (daca se ignora faptul ca numerele ar putea depasi intervalul numerelor reprezentabile pe un intreg), dar determinarea solutiei finale se poate face in $O(1)$ doar pentru ecuatii de gradul doi sau trei, pentru care stim formule de calcul. Pentru ecuatii de grad mai mare nu exista formule generale si trebuie aplicate metode care aproximeaza solutiile. O astfel de metoda ar fi sa derivam polinomul, sa gasim solutiile pentru $P'(x) = 0$, iar apoi sa folosim cate o cautare binara pentru a gasi solutiile $P(x) = 0$.
De exemplu pentru trei numere lipsa $a, b, c$ este usor sa determinam $S{~1~} = a + b + c, S{~2~} = a^2^ + b^2^ + c^2^, S{~3~} = a^3^ + b^3^ + c^3^$. $S{~1~}^2^ = a^2^ + b^2^ + c^2^ + 2ab + 2bc + 2ac = S{~2~} + 2s{~2~}, S{~1~}^3^ = a^3^ + b^3^ + c^3^ + 3a^2^b + 3a^2^c + 3b^2^a + 3b^2^a + 3c^2^a + 3c^2^b + 6abc = S{~3~} + 3(a^2^b + b^2^a + abc) + 3(a^2^c + c^2^a + abc) + 3(b^2^c + c^2^b + abc) - 3abc = S{~3~} + 3ab*s{~1~} + 3ac*s{~1~} + 3bc*s{~1~} - s{~3~} = S{~3~} + 3s{~2~}*s{~1~} - s{~3~}$. Din aceste relatii putem sa obtinem usor $s{~1~}, s{~2~}, s{~3~}$ si apoi putem aplica formulele lui Cardano de rezolvare a ecuatiei de gradul trei pe ecuatia $x^3^ - s{~1~} x^2^ + s{~2~} x - s{~3~} = 0$.
h2(#prob8). Problema 8
Intr-o structura de date avem $n - 1$ numere intregi (pentru simplitate $n = 2^b^ - 1$, cu numere distincte de la $0$ la $n$). Asupra elementelor din structura de date putem face urmatoarea operatie getBit(i, j), care returneaza al $j$-lea bit din reprezentarea binara a numarului $a[ i ]$. Astfel daca $a[ 4 ] = 11$, atunci getBit(4, 3) returneaza $0$ pentru ca $11$ se scrie in baza $2$ ca $1011$. Sa se dea o solutie eficienta care gaseste numarul lipsa.
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, 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(#prob12). Problema 12 ( _JBOI 2011, Bistrita_ )
Se da un sir de $n$ numere naturale in care orice element apare de exact $k$ ori, mai putin $n%k$ dintre acestea care, de asemenea, sunt egale. Sa se determine valoarea elementelor care apar de exact $n%k$ ori. Se garanteaza ca $n%k>0$.
h3. Rezolvare
Se observa ca pentru $k=2$ este de ajuns sa facem xor intre toate elementele sirului. Cum xor este suma bitilor, de pe fiecare pozitie in parte, modulo $2$, pentru $k>2$ scriem fiecare numar in baza $2$ si formam vectorul $x$ cu semnificatia ca $x[i]$ este suma bitilor de pe pozitia $i$ modulo $k$.
La final pozitile nenule din $x$ vor coincide cu pozitile bitilor de $1$ din scrierea in baza $2$ a numarului cautat. Transformam inapoi in baza $10$ si obtinem rezultatul. Complexitatea algoritmului este $O(n*log(P))$, unde $P$ este numarul maxim din sirul dat, iar memoria este $O(log(P))$.
h2(#biblio). Bibliografie
*(#fn1) 1. 'Relatiile lui Viete, _mathworld_ ':http://mathworld.wolfram.com/VietasFormulas.html
*(#fn2) 2. 'Formulele Newton-Girard, _mathworld_ ':http://mathworld.wolfram.com/Newton-GirardFormulas.html
*(#fn3) 3. {'Cycle detection, _wikipedia_ ':http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm}
