233. Number of Digit One

Description

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

 

Example 1:

Input: n = 13
Output: 6

Example 2:

Input: n = 0
Output: 0

 

Constraints:

• 0 <= n <= 109

Solution

number-of-digit-one.py

class Solution:
    def countDigitOne(self, n: int) -> int:
        digits = []

        while n > 0:
            digits.append(n % 10)
            n //= 10

        digits.reverse()
        N = len(digits)

        @cache
        def dp(pos, tight, count):
            if pos == N: return count

            limit = digits[pos] if tight else 9
            res = 0

            for digit in range(0, limit + 1):
                newTight = tight and digit == digits[pos]
                newCount = count + 1 if digit == 1 else count

                res += dp(pos + 1, newTight, newCount)

            return res

        return dp(0, True, 0)