233. Number of Digit One

Posted on Edited on In

233. Number of Digit One

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:

1
2
Input: n = 13
Output: 6

Example 2:

1
2
Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 10^9

Hints/Notes

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
class Solution {
public:
    string s;
    vector<vector<int>> dp;

    int countDigitOne(int n) {
        s = to_string(n);
        dp.resize(s.size(), vector<int>(s.size(), -1));
        int res = dfs(0, 0, true);
        return res;
    }

    // nums can have zeroes in between, no need for isNum
    int dfs(int index, int prev, bool isLimit) {
        if (index == s.size()) {
            return prev;
        }
        if (!isLimit && dp[index][prev] != -1) {
            return dp[index][prev];
        }
        int res = 0;
        int up = isLimit ? s[index] - '0' : 9;
        for (int i = 0; i <= up; i++) {
            res += dfs(index + 1, prev + (i == 1), isLimit && i == up);
        }
        // check status during read and write memo both
        if (!isLimit) {
            dp[index][prev] = res;
        }
        return res;
    }
};