#233

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Digit One

Compute the total number of digit one appearing in all numbers from 0 up to n using state transition dynamic programming for efficiency.

math dynamic programming recursion

Problem Statement

Given a non-negative integer n, determine the total number of times the digit 1 appears in all numbers from 0 to n inclusive. You must handle large n efficiently without iterating through every number.

For example, if n = 13, the numbers from 0 to 13 contain six occurrences of the digit 1. You need to compute this count using an algorithm that combines math reasoning with state transition dynamic programming to account for each digit position.

Examples

Example 1

Input: n = 13

Output: 6

Example details omitted.

Example 2

Input: n = 0

Output: 0

Example details omitted.

Constraints

0 <= n <= 109

Solution Approach

Digit Position Analysis

Break down n by each digit and count the contribution of 1s at each position. For every position, consider higher digits, current digit, and lower digits to compute how many times 1 appears in that place.

Recursive or Iterative DP

Implement a state transition DP where each state represents the current digit index and tightness constraint. Either recursive memoization or iterative bottom-up DP works, tracking counts while respecting number boundaries.

Overflow Prevention and Aggregation

Accumulate counts carefully to avoid integer overflow. Use long or appropriate integer types when summing contributions from each digit position, ensuring correctness for large n.

Complexity Analysis

Metric	Value
Time	O(log_{10}(n))
Space	O(1)

The algorithm processes each digit of n once, leading to O(log_{10}(n)) time complexity. Space complexity is O(1) if iterative aggregation is used, or O(log_{10}(n)) for recursive memoization.

What Interviewers Usually Probe

Checks if candidate recognizes that brute-force counting is too slow and will fail for large n.
Wants a solution that properly models each digit's contribution using DP or mathematical counting.
Looks for handling of boundary cases like n = 0 or digits with zeros in higher places.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the current digit correctly when it is 1, leading to undercounting.
Using naive iteration through all numbers, which exceeds time limits for large n.
Overflowing integer types when summing counts without considering large n.

Follow-up variants

Count digit 'd' instead of 1 across numbers up to n.
Compute number of times a substring appears in decimal representation of numbers up to n.
Adapt the solution for base-k numbers rather than decimal.

FAQ

What is the main pattern used in Number of Digit One?

The primary pattern is state transition dynamic programming applied to digit positions.

Why is naive iteration over all numbers inefficient for this problem?

Because n can be up to 10^9, iterating each number would exceed time limits, making DP necessary.

How do I handle large n without integer overflow?

Use larger integer types or carefully sum counts from each digit position to prevent exceeding limits.

Can this solution be adapted for other digits besides 1?

Yes, the same state transition DP can be applied to count occurrences of any digit across numbers up to n.

Is recursion necessary for this problem?

No, iterative DP can also be used; recursion is optional but must respect state transitions and digit boundaries.

terminal

Solution

Solution 1: Digit DP

This problem essentially asks for the number of times the digit $1$ appears in the given range $[l, ..r]$. The count is related to the number of digits and the value of each digit. We can use the concept of Digit DP to solve this problem. In Digit DP, the size of the number has little impact on the complexity.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def countDigitOne(self, n: int) -> int:
        @cache
        def dfs(i: int, cnt: int, limit: bool) -> int:
            if i >= len(s):
                return cnt
            up = int(s[i]) if limit else 9
            ans = 0
            for j in range(up + 1):
                ans += dfs(i + 1, cnt + (j == 1), limit and j == up)
            return ans

        s = str(n)
        return dfs(0, 0, True)

Continue Practicing

#241 different ways to add parentheses #486 predict the winner #509 fibonacci number