How to search for the number of numbers that satisfy a condition in the interval [x, y]?

Question

Algorithms

Good day! There is such a task:
In the interval [1, 2300000] it is necessary to find such numbers in which there is a sequence of digits that sums up the number 10, and at the same time, the sequence must include the number 5.
For example , 523 014 is suitable, and 2341 87 - no. How to algorithmically correctly implement the problem? I don't want to build 2300000 lines and then analyze each one.
Well, or at least build only numbers containing 5 in a given interval.

Answer 1

Probably, it is necessary not to search, but to generate such a sequence.
One of the numbers must already be "5". For the rest, it is necessary to collect all options (taking into account the order) of expanding 5 into a sum of digits: from 11111to 5.
Now you need to collect all the options for placing the five and each of the combinations that fit into the range [1 .. 23е5]. You can type recursively from left to right. Numbers are good for the first position 0, 1, 2. On the second with the first "2" 0, 1, 2, 3, or any with 0 or 1. From the third to the seventh - any.
For each option for dialing the sum, there are still all options for the position of non-participating digits.

Answer 2

The restrictions are small - the easiest way is to stupidly sort through all the numbers up to 23 million, convert each to a number and check for compliance with the condition. You can speed up the checks a little if you quickly count the sum of digits and the number of '5's in the substring using partial sums (count the sum and the number of 5 digits in each prefix of the string. Then subtract the values ​​for one prefix from the values ​​of the shorter one - the values ​​for the substring remain) .