Koba
Solutia 1 (neoptima)
O solutie neoptima ar fi parcurgerea de la 1 la N si adaugarea fiecarei cifre cerute la suma. Acest lucru se face folosind doar ultimele cifre din numere, pentru a nu implementa pe numere mari, cu formula Ti=(Ti-1+Ti-2*Ti-3) % 10. Complexitatea acestei solutii este O(N).
Solutia 2
Pentru o solutie optima, se observa ca, de la un moment dat, sirul devine periodic. Fie numarul abc care reprezinta 3 cifre a, b si, respectiv, c.
Tinem un vector in care A[abc] va reprezenta pozitia pe care a aparut tripletul a, b, c in sirul pe care l-am construit pana la momentul respectiv. Parcurgand cu un indice i de la 1 la N si adunand in suma S cifrele folosite pana la momentul actual, daca la un moment dat, un triplet a, b, c va aparea pentru a doua oara, facem suma cifrelor (notata cu Sum) de la ultima aparitie a celor 3 cifre pana la momentul actual si memoram in M numarul de cifre din aceasta suma (i-A[abc]+1). In acest moment, stim suma cifrelor pana la pasul i. Acum trebuie aflata suma cifrelor de la i+1 la N. Pentru a afla acesta suma, scadem din N pe i (pentru a afla suma cifrelor de dupa i) si vedem de cate ori intra in "noul" N acea secventa "periodica" si adunam (N/M)*Sum la S. Pana acum am calculat suma cifrelor pana la cel mai mare multiplu al lui M mai mic decat N. De aici mai adaugam la S primele N%M cifre din partea periodica.
