Problem

Given a single-digit integer d and two integers low and high, return the number of times thatd occurs as a digit in all integers in the inclusive range[low, high].

Examples

Example 1:

1
2
3
4

Input: d = 1, low = 1, high = 13
Output: 6
Explanation: The digit d = 1 occurs 6 times in 1, 10, 11, 12, 13.
Note that the digit d = 1 occurs twice in the number 11.

Example 2:

1
2
3

Input: d = 3, low = 100, high = 250
Output: 35
Explanation: The digit d = 3 occurs 35 times in 103,113,123,130,131,...,238,239,243.

Constraints:

  • 0 <= d <= 9
  • 1 <= low <= high <= 2 * 10^8

Solution

Method 1 – Digit DP (Dynamic Programming on Digits)

Intuition

To count how many times digit d appears in all numbers from 1 to n, we use digit dynamic programming (digit DP). We count for all numbers up to high, then subtract the count for all numbers up to low-1.

Approach

  1. Define a recursive DP function that, for each position, tracks:
    • The current position in the number.
    • Whether the number is tight (i.e., still matches the prefix of the bound).
    • The count of digit d so far.
  2. For each digit position, try all possible digits (0 to 9), and for each, recurse to the next position.
  3. If the current digit is d, increment the count.
  4. Use memoization to avoid recomputation.
  5. For d == 0, handle leading zeros carefully (do not count leading zeros).
  6. The answer is count(high) - count(low-1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def digitsCount(self, d: int, low: int, high: int) -> int:
        def count(n: int) -> int:
            s = str(n)
            from functools import lru_cache
            @lru_cache(None)
            def dp(pos: int, tight: bool, lead: bool) -> int:
                if pos == len(s):
                    return 0
                ans = 0
                up = int(s[pos]) if tight else 9
                for dig in range(0, up+1):
                    nlead = lead and dig == 0
                    nans = dp(pos+1, tight and dig == up, nlead)
                    if dig == d and not (nlead and d == 0):
                        nans += 1 if pos != len(s)-1 or not nlead else 0
                    ans += nans
                return ans
            return dp(0, True, True)
        return count(high) - count(low-1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int digitsCount(int d, int low, int high) {
        return count(high, d) - count(low - 1, d);
    }
    private int count(int n, int d) {
        char[] s = Integer.toString(n).toCharArray();
        Integer[][][] memo = new Integer[s.length][2][2];
        return dp(0, 1, 1, s, d, memo);
    }
    private int dp(int pos, int tight, int lead, char[] s, int d, Integer[][][] memo) {
        if (pos == s.length) return 0;
        if (memo[pos][tight][lead] != null) return memo[pos][tight][lead];
        int ans = 0;
        int up = tight == 1 ? s[pos] - '0' : 9;
        for (int dig = 0; dig <= up; ++dig) {
            int nlead = lead == 1 && dig == 0 ? 1 : 0;
            int nans = dp(pos+1, (tight == 1 && dig == up) ? 1 : 0, nlead, s, d, memo);
            if (dig == d && !(nlead == 1 && d == 0)) {
                nans += (pos != s.length-1 || nlead == 0) ? 1 : 0;
            }
            ans += nans;
        }
        return memo[pos][tight][lead] = ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log n * 2 * 2 * 10), since we have up to 10 digits, 2 tight/lead states, and 10 possible digits per position.
  • 🧺 Space complexity: O(log n * 2 * 2), for the DP memoization table.