Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.


Let’s try to solve this problem by dividing it into smaller quizzes:

For example, to caculate the result for 2954:

• count(2954)=count(2000)+count(954)
• count(954)=count(900)+count(54)
• count(54)=count(50)+count(4)

Now we got the conclusion that count(2954)=count(2000)+count(900)+count(50)+count(4), which is leading us to the question of how to get count(i*10^j)

To calculate count(i*10^j), we separate the ‘1’s we are looking for into two groups:

• 1s appearing in the highest digit, like the first ‘1’ in the number 1111.
• For numbers starting with 1, this part is the lower part number plus one. Let’s take 1599 as an example. From 1000 to 1599 we got 599+1=600 ‘1’s at the highest digit.
• For numbers not starting with 1, this part is always 10^math.floor(log10(number)). Like for 2000, from 1000 to 1999 we got 1000 ‘1’ which is equal to 10^3.
• 1s appearing in the lower digits, like the last 3 ‘1’s in the number 1111.
The formula to calulate this part is: (highest digit) * count(10^math.floor(log10(number)-1)). Like for 3000, the result is 3*count(999)

At this point, the last puzzle we need to solve is to find a way to calculate count(10^n-1). Let’s take a look at some examples:

• For number ranging from 1-99 we got 1 one.
• For number ranging from 1-999 we got 20 ones.
• For number ranging from 1-9999 we got 300 ones.

After some observations, we can see count(10^n-1)=count(10^(n-1)-1)*10+10^(n-1). Combining this with an initial case of count(9)=1, we can extrapolate that count(10^n-1)=n*10^(n-1).

With all these deductions in mind, we can finally solve the original problem with DP.
I implemente this idea with the help of stack to avoid recursion and below is the code