Fetite

Vom rezolva problema recursiv. Fie f(N) numarul de ordine al ultimei petale ramase in cazul in care avem la inceput o floare cu N petale. Se disting 2 cazuri:

• N este un numar par. Vor fi eliminate toate petalele pare si ne vom intoarce la petala 1. Putem considera ca am redus jocul la N/2 petale, singurul lucru de care trebuie sa avem grija este renumerotarea petalelor. Deducem ca f(N) = 2 * f(N/2) - 1.
• N este un numar impar. Vor fi eliminate toate petalele pare si apoi vom elimina petala numarul 1. Vom ajunge la petala 3, si observam ca am redus din nou jocul la N/2 petale. Din renumerotare rezulta f(N) = 2 * f(N/2) + 1.

Complexitatea acestui algoritm este O(log N).