Easy to understand python solution, can generalized to 0 to 9


  • 2
    P
    class Solution(object):
        def countDigitOne(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n < 1:
                return 0
            result = 0
            # number of appearances for one cycle when 1 appears at position i
            i = 1
            while n >= i:
                # complete cycle, one more complete cycle if current digit > 1
                cycle = n / (i * 10) + (1 if n / i % 10 > 1 else 0)
                result += cycle * i
                # incomplete cycle if current digit == 1
                if n / i % 10 == 1:
                    result += n % i + 1
                i *= 10
            return result
    

    A cycle is 0~9 for one position. 1 appears a certain number of times in each cycle.

    For example, given number 32107.

    At position 7, 1 appears 3210 complete cycles, and within each cycle 1 appears once. Also, because 7 > 1, so it can be regarded as one more complete cycle. In total 1 appears 3211 times at position 7.

    At position 0, 1 appears 321 complete cycles, and within each cycle 1 appears 10 times, eg, ...10-...19. In total 1 appears 321 * 10 times at position 0.

    At position 1, 32 complete cycles, and within each cycle 1 appears 100 times, eg, ..100-..199. Notice here it is 1, so it has incomplete cycle from 32100-32107, which is 32107 % 100 + 1 = 8 times. In total 1 appears 32 * 100 + 8 times at position 1.

    So on so forth.

    A generalized code for any digit 0 ~ 9 is below.


  • 0
    P
    This post is deleted!

  • 0
    P
    class Solution(object):
        def countDigitOne(self, n):
            """
            :type n: int
            :rtype: int
            """
            def countDigitX(x, n):
                if n < x:
                    return 0
                result = 0
                # number of appearances for one cycle when x appears at position i
                i = 1
                while n >= i:
                    # complete cycle, one more complete cycle if current digit > x
                    cycle = n / (i * 10) + (1 if n / i % 10 > x else 0)
                    result += cycle * i
                    # incomplete cycle if current digit == x
                    if n / i % 10 == x:
                        result += n % i + 1
                    i *= 10
                return result
            return countDigitX(1, n)
    

Log in to reply
 

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