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