Editorial for The Polar Express
Submitting an official solution before solving the problem yourself is a bannable offence.
For of points, we can iterate the through all integers in the range , and check the number of distinct values.
Time Complexity: .
For the remaining of points, we can solve the problem with dynamic programming. Firstly, observe that the values of are in the range . Let be the number of numbers less than or equal to such that the sum of their digits is equal to . The value of can be determined with dynamic programming, more specifically, digit dynamic programming. Let be the number of ways to obtain a sum of with digits remaining, while still being less than or equal to . Thus our DP recurrence is:
The answer is thus the number of non-zero values of , for each value of in the range .
Time Complexity: , with a large constant factor.