Pseudocod:
getMissing(V, n):
current_vec = V
current_bit = 31
result = 0
while (getBit(n+1, current_bit) == 0)
current_bit--
while (current_bit >= 0)
setBit0 = {}
setBit1 = {}
for (element : current_vec)
if (getBit(element, current_bit) == 0)
setBit0.add(element)
else
setBit1.add(element)
if (setBit0.size != (1 << current_bit))
result |= (1 << current_bit)
current_vec = setBit1
else
current_vec = setBit0
return result
Conditita problemei :
Se dă un șir neordonat S cu n - 1 numere distincte, selectate dintre cele n numere de la 0 la n - 1 . Toate sunt numere întregi, reprezentate pe 32 de biți. Folosind metoda getBit(int i, int j) care întoarce al j -lea bit din reprezentarea binară a lui S[i] , determinați numărul lipsă.
Exemplu:
- pentru șirul {0 1 9 4 5 7 6 8 2} lipsește numărul 3
- getBit(7,3) întoarce al treilea bit din S[7]. S[7] este 8, în binar: 1000, deci bit-ul 3 este 1.
- La un prim pas, se observă că bitul 3 este 0 pentru doar 7 numere din șir, deși între 0 și 9 sunt 8 numere care ar trebui să aibă bitul 3 egal cu 0, respectiv numerele de la 0 la 7. Prin urmare, la primul pas ne dăm seama că numărul căutat este între 0 și 7.