PCLP Laborator12 : Problemset (extra)

Probleme extra propuse pentru PCLP Laborator12.

Rezolvați următoarele probleme de pe Leetcode folosind exclusiv operații pe biți:

  1. Reverse bits Hint: Parcurgeți biții numărului de la cel mai puțin semnificativ la cel mai semnificativ și construiți rezultatul folosind deplasări și operații OR.

  2. Counting bits Hint: Numărul de biți de 1 ai unui număr poate fi derivat dintr-un număr mai mic folosind o operație pe biți deja cunoscută.

  3. Single element Hint: Analizați fiecare poziție de bit separat și observați ce se întâmplă când un bit apare de trei ori.

  4. Single pair of elements Hint: Folosiți XOR pentru a elimina elementele duplicate și separați rezultatul folosind un bit diferit între cele două valori unice.

  5. Bitwise AND Hint: Biții care diferă între capetele intervalului vor deveni 0 în rezultat; căutați prefixul comun al celor două numere.

Probleme de interviu

Pentru cei interesați, recomandăm rezolvarea și următoarelor probleme, care sunt des întâlnite la interviuri.

Atenție! Problemele din această categorie au un nivel de dificultate ridicat, peste cel cerut la cursul de PC. Recomandăm totuși rezolvarea acestor probleme pentru cei care doresc să aprofundeze lucrul cu operații pe biți.

Swap bits

Se dă un număr n natural pe 32 de biți. Se cere să se calculeze numărul obținut prin interschimbarea biților de rang par cu cel de rang impar.

Exemplu: n = 2863311530 = > m = 1431655765

Hint: Reprezentarea numerelor în baza 2 (convertor).

Element unic din șir

Fie un șir cu 2n + 1 numere întregi, dintre care n numere apar de câte 2 ori, iar unul singur este unic. Să se gasească elementul unic.

Exemplu:

  • n = 5 și sirul [1, 4, 4, 1, 5]
  • Numărul unic este 5.

Hint: Încercați să nu folosiți tablouri.

Follow-up 1: Șirul are (2*n + (2 * p + 1)) numere. Se sție că un singur număr apare de un număr impar de ori (2p + 1), iar celelalte apar de un număr par de ori. Cum găsiți numărul care apare de un număr impar de ori?

Exemplu:

  • n = 5 și sirul [1, 1, 4, 4, 4, 4, 5, 5, 5]
  • Răspunsul este 5.

Follow-up 2: Șirul are (2n + 2) numere, n numere apar de câte 2 ori, iar 2 numere sunt unice. Cum găsiți cele 2 numer unice?

Exemplu:

  • n = 5 și sirul [1, 4, 4, 1, 5, 6]
  • Numărele unice sunt 5 și 6.

TODO: sursă

Căutare binară pe biți

Realizează o funcție de căutare pe binară, utilizând operații pe biți pentru optimizarea acestei implementări.

Follow up: Puteți găsi alt algoritm care să nu se bazeze pe împarțirea vectorului în două și compararea elementului din mijloc cu cel cautat?

Hint: caut bin și Multe "smenuri" de programare in C/C++... si nu numai!

Jocul NIM

Se dau n grămezi, fiecare conţinând un anumit număr de pietre. Doi jucători vor începe să ia alternativ din pietre, astfel: la fiecare pas, jucătorul aflat la mutare trebuie să îndepărteze un număr nenul de pietre dintr-o singură grămadă. Câştigătorul este cel care ia ultima piatră. Să se determine dacă jucătorul care ia primele pietre are strategie sigură de câştig.

Exemple:

  • n = 4, gramezi = [1 3 5 7], raspuns = NU
  • n = 3, gramezi = [4 8 17], raspuns = DA

Hint: nim

Sushi

Enunt: sushi