Take the number 987654321 as input.

for [0,10^8) there are 8*10^8/10 ones ,because there 8*10^8 digits and each number (0,1,2,3,4,5,6,7,8,9) has the same probability to appear so the number of ones is 8*10^8/10;

[2*10^8,3*10^8), [3*10^8,4*10^8), ... , [8*10^8,9*10^8) all have 8*10^8/10 ones;

[10^8,2*10^8) has 8*10^8/10 + 10^8 ones (easy to understand)

so just remain [9*10^8,987654321], which equals to [0,87654321], recursion.

Just be aware that the variable **num** in Solution() should be long long. ^-^

```
class Solution {
public:
int countDigitOne(int n) {
if (n <= 0) return 0;
int len = 0;
int num = n;
while (num) {
len++;
num /= 10;
}
int base = 1;
for (int i = 0; i<len - 1; i++) base *= 10;
int firstdigit = n / base;
int ret = countDigitOne(n%base);
if (firstdigit == 1) return a[len - 1] + n%base + 1 + ret;
else return firstdigit*a[len - 1] + base + ret;
}
Solution() {
for (int i = 0; i<10; i++) {
long long num = 1;
for (int j = 0; j<i; j++) num *= 10;
a.push_back(i*num / 10);
}
}
private:
vector<int> a;
};
```