1067. Digit Count in Range

Posted on Edited on In

1067. Digit Count in Range

Description

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

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

Hints/Notes

  • 2024/11/19
  • digit dp with lower bound and is_num
  • premium

Solution

Language: C++

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int d;
    string lowStr, highStr;
    vector<vector<int>> dp;

    int digitsCount(int d, int low, int high) {
        this->d = d;
        highStr = to_string(high);
        lowStr = to_string(low);
        int n = highStr.size();
        dp.resize(n, vector<int>(n, -1));
        lowStr = string(n - lowStr.size(), '0') + lowStr;
        int res = dfs(0, 0, true, true, false);
        return res;
    }

    int dfs(int index, int count, bool limit_low, bool limit_high, bool is_num) {
        if (index == highStr.size()) {
            return is_num ? count : 0;
        }

        if (!limit_low && !limit_high && is_num && dp[index][count] != -1) {
            return dp[index][count];
        }

        int res = 0;
        if (!is_num && lowStr[index] -'0' == 0)
            res += dfs(index + 1, count, true, false, false);

        int lo = limit_low ? lowStr[index] - '0' : 0;
        int hi = limit_high ? highStr[index] - '0' : 9;
        for (int i = max(lo, 1 - is_num); i <= hi; i++) {
            res += dfs(index + 1, count + (i == d), limit_low && i == lo, limit_high && i == hi, true);
        }
        if (!limit_low && !limit_high && is_num) {
            dp[index][count] = res;
        }
        return res;
    }
};