233. Number of Digit One

Description

image-20210813235350161

Solution

We can calculate the number of one on each digit, for example

1
2
3
To count one's number on 1234567
we can count one on 1, 10, 100...
If we need to count one on 100, we can have 1234 * 100 + 100

So we can have

1
2
k's digit count = [n/10^(k+1)] * 10 ^ k + 
								min(max(n mod 10^(k+1) - 100, 0), 10^k)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long long mulk = 1;
        int ans = 0;
        for (int k = 0; n >= mulk; ++k) {
            ans += (n / (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
            mulk *= 10;
        }
        return ans;
    }
};