Python: more general question - count a given digit d


  • 0
    N

    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:

    1. the number at x_th position > d
      in this case, subproblem count = (a+1) * 10^(i-1)
    2. the number at x_th position == d
      in this case, subproblem count = a * 10^(i-1) + (b+1)
    3. 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
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.