# Share my solution: c++, 0ms

• Take the number 987654321 as input.

for [0,10^8) there are 810^8/10 ones ,because there 810^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;

[210^8,310^8), [310^8,410^8), ... , [810^8,910^8) all have 8*10^8/10 ones;

[10^8,210^8) has 810^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;
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.