Here is a simple implementation for this issue. And it's TC is O(n/10), O(n);
Any better one is expected.
1 int onenumber(int n)
2 {
3 if(n <= 0) return 0;
4 if(n <= 9) return 1;
5
6 int bak = n, hig = 1, num = 0;
7 while(n >= 10) {
8 hig *= 10;
9 n /= 10;
10 }
11
12 if(n == 1) {
13 num = bak-hig+1 + ((bak-hig == 0) ? 0 : (bak-hig <= 9 ? 1 : onenumber(bak-hig)));
14 num += (hig-1 <= 9 ? 1 : onenumber(hig-1));
15 }
16 else {
17 num = (bak - n*hig == 0 ? 0 : (bak - n*hig <= 9 ? 1 : onenumber(bak - n*hig)));
18 num += (n*hig-1 <= 9 ? 1 : onenumber(n*hig-1));
19 }
20
21 return num;
22 }