Ridicarea rapidă la putere
Cât costă să calculezi 2¹⁰⁰? Varianta școlară face 99 de înmulțiri. Varianta „împarte și stăpânește” face doar câteva: înjumătățește exponentul la fiecare pas, deci O(log n). Ideea stă la baza criptografiei (de exemplu RSA) și apare des la interviuri.
Scrie funcția recursivă putere(x, n) care returnează un tuplu (rezultat, inmultiri): valoarea xⁿ și numărul de înmulțiri făcute. Cazuri de bază: n == 0 -> (1, 0) și n == 1 -> (x, 0). Pătratul jumătății adaugă o înmulțire, iar înmulțirea sup…
- Tratează cele două cazuri de bază.
- Apelează o singură dată putere(x, n // 2) și ridică rezultatul la pătrat (+1 înmulțire).
- La n impar, înmulțește cu x (+1). Trebuie să apară: (1024, 4), (1594323, 5), (1, 0), 8.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan