Cine ma ajuta din un pseudocode sa faca in c++

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.

@Lucian1 noi te putem ajuta doar dacă ai făcut ceva și te-ai încurcat. Nu îți facem temele.

2 Likes