Let ~f(n, prefix)~ consider all numbers in the interval ~[prefix \cdot 10^n, (prefix+1) \cdot 10^n)~. The function calculates the total contribution towards the result of ~n~ digits yet to be placed to the right of the given prefix.

To calculate ~f~, we add a group of any digit other than the last one in prefix. For example, suppose ~n = 4~ and ~prefix = 112~. ~f(4, 112)~ considers the numbers ~1\,120\,000~ through ~1\,129\,999~. If we decide to append the group ~55~ to the number, the contribution of this recursive branch is ~5^2 + f(2, 11\,255)~.

It may seem that it takes too many recursive calls to calculate the result. However, many of these yield the same result for different prefixes, more precisely when the entire interval considered is contained inside ~[A, B]~. For these cases, we can memoize the result (it depends only on ~n~). There are only ~\mathcal O(\log B)~ recursive calls in which we branch without memoization.