My idea is to count every digit 1 at every digits.

At each step, First calculate the maximum number of 1 it can get,

and then deduct the excessive 1 it gets.

Take 13 for example:

Start from units,

max = (13+9)/10 * 1 = 2 <--- 1, 11

temp = 10-(8+13%10+1) = -2 <--- it indicates that we don't have to deduct anything.

tens,

max = (13+90)/100 * 10 = 10 <--- 10,11,12,13,14,15,16,17,18,19

temp = 100 - (80+13%100+1) = 6 <-- so we have to deduct 6(14,15,16,17,18,19).

```
public int countDigitOne(int n) {
long i=1;
long sum=0;
for(int j=0;j<10;j++){
sum += (n+9*i)/(i*10) * i;
long temp = 2*i-(n%(i*10))-1; // or long temp = 10*i-(8i+n%(i*10)+1)
if(temp<i && temp >0)sum -=temp;
i*=10;
}
return (int)sum;
}
```