Analiza

Način 1

Primetimo da različitih cifara koje mogu da se pojavljuju u broju može da ima najviše 10, tako da možemo uraditi zadatak sledećim postupkom: fiksiramo najmanju i najveću cifru (njihove vrednosti) koje ostaju u broju, i vidimo da li u ~K~ operacija možemo izbrisati sve cifre koje su manje od najmanje i veće od najveće. Ukoliko možemo, razlika kvadrata te dve cifre je jedan od kandidata za rešenje, a nama od svih kandidata treba onaj maksimalni.

Način 2

Ukoliko sortiramo (nekim ~O(N \log N)~ algoritmom) sve cifre našeg broja, primetimo da će u optimalnom rešenju biti uzastopni podniz tog sortiranog niza (dužine ~N - K~). Takvih podnizova ima ~O(N)~, pa možemo proći kroz sve i izabrati onaj koji daje maksimalnu razliku kvadrata.

Smernice za algoritam

Ukoliko koristimo prvi način potreban nam je brojač pojavljivanja svake cifre u broju kako ne bismo svaki put kad brojimo prolazili kroz ceo broj - složenost implementacije može varirati, ali postoji 10 cifara, tako da bilo šta što koristi nekoliko petlji te dužine prolazi. Ukoliko koristimo drugi način, u ukupnoj složenosti dominira složenost sortiranja - ~O(N \log N)~ za neki standardni sort, ~O(N)~ ukoliko koristimo counting sort.