How to find the number of numbers from 1 to 10^9 that have the sum of the digits = x?

Question

Algorithms

Given a single number X.
You need to find the number of numbers from 1 to 10^9 that have the sum of the digits of X.
For example, if X = 1, the answer will be 10.
I can’t find a pattern. With x = 1, everything is clear - we count the powers of ten and that's it, but what to do with other numbers?

Answer 1

If you can't find a pattern, look it up.

Answer 2

I don't think there is any pattern. Just solve a problem that looks something like this: Find all sets of N numbers that give the number X, the first number is not zero. Having solved this problem, getting an answer for yours is very easy.
Another option is of course even simpler, just run through all the numbers and calculate the sum of the numbers.
The advantage of the first solution is that the 10^9 limit is easily overcome and you don't have to think about overflows and so on.

Answer 3

Head-on.
I sketched out the code in ruby, but already with a million, noticeable time is spent on the calculation. So it's better to use some compiling PL, then it will probably be faster.

Answer 4

10^9, ... For example, if X = 1, the answer is 10.

For x=1, the result will be 9, because 9 digits if up to 10^9 ) (i.e. not including)
From here - the largest value will be 9x9 = 81, resulting in = 1, and 80 will give = 9, 79 -> 45, 78 -> 165 [0 ..81], the remaining values ​​will give 0. As a result, it turns out, as it were, an inverse parabola with a vertex somewhere in the middle.
In order not to sort through the whole billion, you can do a full recursion - to go through only the final values, i.e. for example, with X \u003d 3, the first digit first takes on 1, which means 2 goes to the rest, then the 1st digit takes on 2, the rest goes 1, etc.
But in general, if you “draw on a piece of paper”, it becomes obvious that this problem can be solved using statistics: with an increase in X, the “space” for placement decreases, but the number of elements for placement increases, and the results of lower X can be used in older ones.