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 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 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 ^&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$