Simpla
Pornim de la observaţia că în intervalul [0, 10n-1] există exact jumătate numere naturale cu suma cifrelor pară. Rezultă că avem 5 * 10n-1 numere naturale cu suma cifrelor pară. Pentru a rezolva problema pe intervalul [a, b], vom folosi o funcţie f(x) egală cu numărul numerelor cu suma cifrelor pară din intervalul [0, x]. Astfel, rezultatul va fi f(b) - f(a - 1).
Pentru a calcula valoarea returnată de un f(x), să presupunem că x = x1x2..xm-1xm. Avem f(x) = x1 * 5*10m-2 + x2 * 5*10m-3 + .. + xm-1 * 5 + v. Acest lucru este posibil deoarece pentru un xi nu are importanţă suma x1 + .. + xi-1, întrucât numărul numerelor cu suma cifrelor pară este egal cu al celor cu suma cifrelor impară. Cazul ultimei cifre, se tratează prin a considera toate numerele cuprinse în intervalul [x - xm, x] care se vor aduna la rezultat dacă au suma cifrelor pară, rezultat reţinut în v în formula de mai sus. Sau mai simplu, f(2*k+1) = k si f(2*k) = f(2*k+1)-(1-S(2*k+1))%2, unde S(x) = suma cifrelor lui x.
