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") ==
 
(Categoria _Algoritmi_, Autor _Cosmin Negruseri_)

(toc){width: 25em}*{text-align:center} *Cuprins*
* 'Problema 1 ( _interviu Microsoft_ ) ':missing-numbers#prob1

* '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 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
h2(#prob1). Problema 1 ( _interviu Microsoft_ )

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)$ ).

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 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).

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 ^&and;^ ) si proprietatile ei $a ^&and;^ a = 0$ si $a ^&and;^ b = b ^&and;^ a$. Vom face suma xor a numerelor $a[i] ^&and;^ i$ (1 <= i <= n):
$S = a[ 1 ] ^&and;^ 1 ^&and;^ a[ 2 ] ^&and;^ 2 ^&and;^ ... ^&and;^ a[ n - 1 ] ^&and;^ n - 1 ^&and;^ n$

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.

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

...
$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 determin�� 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$.

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 <code>getBit(i, j)</code>, care returneaza al $j$-lea bit din reprezentarea binara a numarului $a[ i ]$. Astfel daca $a[ 4 ] = 11$, atunci <code>getBit(4, 3)</code> returneaza $0$ pentru ca $11$ se scrie in baza $2$ ca $1011$. Sa se dea o solutie eficienta care gaseste numarul lipsa.

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

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]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

*(#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}

3702