try to solve a more general version: count the total number of digit d ( 1<= d <= 9)
In essence, the method is the same as this post.
And I brief the idea again here:
the total appearance of digit d = sum( the appearance of d at i_th decimal position for possible i's)
Therefore the sub problem of this question is: the appearance of d at i_th decimal position, where 1 <= i <= log10(n).
When count the appearance of d at i_th position, we decompose number n into this three component n = "axb", where x is the number at i_th position. For example, if n = "43210", when counting the appearance of d at 2nd decimal position (tens-digit), n is decomposed to a = 432, x = 1, b=0.
This problem can be resolved by considering these three scenarios:
- the number at x_th position > d
in this case, subproblem count = (a+1) * 10^(i-1)
- the number at x_th position == d
in this case, subproblem count = a * 10^(i-1) + (b+1)
- the number at x_th position < d
in this case, subproblem count = a * 10^(i-1)
def count_digit(n, digit): c = 0 div = 1 while div <= n: a = n/div b = n%div x = a%10 if x > digit: c += (a/10 + 1) * div elif x == digit: c += b + 1 + (a/10) * div else: c += (a/10) * div div *= 10 return c