Skip to content

233. Number Of Digit One

Math Dynamic Programming Recursion

Problem - Number Of Digit One

Hard

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def countDigitOne(self, n: int) -> int:
        s = str(n)

        @lru_cache
        def dfs(i: int, count: int, lim: bool) -> int:
            if i >= len(s):
                return count

            dig = int(s[i]) if lim else 9
            result = 0
            for j in range(dig + 1):
                result += dfs(i + 1, count + (j == 1), lim and j == dig)

            return result

        return dfs(0, 0, True)

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.6 MB (91.26%)