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
Python3
class Solution:
def countDigitOne(self, n: int) -> int:
s = str(n)
N = len(s)
digits = list(map(int, s))
@cache
def dp(index, tight, count):
if index == N:
return count
limit = digits[index] if tight else 9
res = 0
for digit in range(limit + 1):
res += dp(index + 1, tight and digit == digits[index], count + 1 if digit == 1 else count)
return res
return dp(0, True, 0)