We will describe two ways to approach the problem.

The "classic" approach is to develop the function ~f(N, S) =~ how many integers less than or equal to ~N~ have the digit-sum ~S~. The solution is then ~f(B, S) - f(A-1, S)~.

To calculate the value of ~f~, we use an auxiliary function ~g(len, S) =~ how many integers of length ~len~ have the digit-sum ~S~. The function ~g~ is easy to calculate using dynamic programming.

Suppose ~N~ is ~L~ digits long and its first digit is ~D~. Then ~f(N, S) = g(L-1, S) + g(L-1, S-1) + \dots + g(L-1, S-D+1) + f(N-D \cdot 10^{L-1}, S-D)~. This can be calculated iteratively.

An alternative approach is to recursively build the number and take advantage of many subproblems sharing the same solution. Suppose that, in our recursive function, we have decided on a prefix ~P~ of the number. Then we know exactly what range of numbers can be built hereafter: if we put ~K~ more zeros, we get ~P \cdot 10^K~. If we put ~K~ nines, we get ~P \cdot 10^{K+1}-1~.

If this entire range is outside the interval ~[A, B]~, then we return ~0~. If the entire range is inside the interval, then the solution is equivalent to calculating the function ~g~ from above (this is where many subproblems share the same solution). If the range is partially inside ~[A, B]~, then we just continue the recursion (try every digit). The key is to notice that this last case will happen only ~\mathcal O(\log B)~ times, so this solution will be as efficient as the first one. The accompanying source code demonstrates the second approach in a single function.

We can find the smallest integer with the digit-sum ~S~ while calculating the total number of integers.

An alternative is to use binary search to find the first number ~X~ such that the interval ~[A, X]~ contains exactly one integer with the digit-sum ~S~ (this is equivalent to the first half of the problem).