Analiza

Da bismo mogli da nađemo minimalan broj operacija za izjednačavanje svih kula, prvo nam je potreban način da odredimo minimalan broj operacija potreban da bi se jednoj kuli dodalo ~K~ kockica. Ovo nije moguće ako ~K = 1~, jer je svaka operacija dodaje barem dve kockice. Ako ~K \leq 2~, optimalan algoritam je:

• dok ~K~ nije deljivo sa ~3~, dodaj dve kockice (i samim time smanji ~K~ za ~2~)
• dodaj ~K/3~ grupa od po tri kockice

Jasno je da je ovaj algoritam optimalan u slučaju u kom je ~K~ deljivo sa ~3~. Ako ~K~ nije deljivo sa ~3~, sigurno moramo da iskoristimo barem jednu grupu od dve kockice, a ako pretpostavimo da je naš algoritam optimalan za ~K-2~ kockice, po indukciji je optimalan za svako ~K~ (gde su bazni slučajevi ~K=2~ i ~K=3~, za koje je potrebna jedna grupa).

Primetimo da ove vrednosti (minimalni brojevi operacija) rastu sa K (počev od ~K=2~, vrednosti su: ~1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, \dots~ -- svaka posle ~1~ se ponavlja tri puta). Dakle, minimalan ukupan broj operacija se postiže tako što odaberemo najmanju "ciljnu visinu" ~T~ na koju možemo dovesti visine svih kula.

Pošto ne možemo "smanjivati" kule, ovo ~T~ mora biti veće ili jednako od svih vrednosti ~A_i~. Takođe ne sme biti jednako sa ~A_i~ ni za jedno ~i~, pošto kule ne možemo povećati za samo jednu kockicu. Ako je ~M~ maksimalna vrednost u nizu ~A_i~, imamo dve mogućnosti:

• ~M-1~ se ne javlja u ~A~ -- optimalno je ~T=M~
• u suprotnom, ne možemo koristiti ~T=M~ (zbog ~M-1~) ni ~T=M+1~ (zbog ~M~) -- optimalno je ~T=M+2~

Nakon što odredimo optimalnu vrednost za ~T~, potrebno je samo da saberemo broj potrebnih kockica za svaku kulu na osnovu opisanog algoritma. Kako ~T~ možemo odrediti jednim prolazom kroz niz (gde pamtimo najveći i drugi najveći element), a broj dodatih kockica u ~\mathcal{O}(1)~ po kuli (jer ćemo najviše dvaput dodati dve kockice), ukupna složenost algoritma je ~\mathcal{O}(N)~.