The idea is same as most posts. The good thing is that we don't need to calculate log10(n) in each iteration here and it's non-recursive.

```
int countDigitOne(int n) {
if (n < 0) return 0;
int a[10] = { 0 }, b[10] = { 1 };
for (int i = 1; i < 10; i++) {
b[i] = b[i - 1] * 10;
a[i] = a[i - 1] * 10 + b[i - 1];
}
string nStr = to_string(n);
int ans = 0;
for (int i = 0, size = nStr.size(); i < size; i++) {
int digit = nStr[i] - '0';
if (digit > 1) {
ans += a[size - i - 1] * digit + b[size - i - 1];
} else if (digit == 1) {
ans += a[size - i - 1] + 1;
if (i != size - 1) ans += stoi(nStr.substr(i + 1));
}
}
return ans;
}
```