h1. Probleme cu numere lipsa si nu numai ...

h1. Probleme cu numere lipsa si nu numai...

== include(page="template/implica-te/scrie-articole" user_id="alecman") ==

(Categoria _Diverse_, autor _Cosmin Negruseri_)

(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$

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