The idea is check number of 1 for each 10,100,1000,10000 ... position. For example, for 312:

check 000~099, 100~199, 200~299, 300~312 and sum them up, for 000~099 and 200~299, it's countDigitOne(99), for 100~199 it's 100+countDigitOne(99), and for 300~312 it's countDigitOne(12).

```
int countDigitOne(int n, int x){
if(n == 0) return 0;
if(n<10 || x==1) return 1;
if(n/x == 1) return n-n/x*x+1+countDigitOne(n-n/x*x)+countDigitOne(x-1);
return x+n/x*countDigitOne(x-1)+countDigitOne(n-n/x*x);
}
int countDigitOne(int n) {
if(n <= 0) return 0;
int x = 1, y=n;
for(;y>=10;x*=10,y/=10);
return countDigitOne(n, x);
}
```