As long as we have learned permutation and combination in mathematics, we will not try to use brute-force method to hack this one. Before we move any further, tell me how many ones in 9? the answer is 1; there will be 0, 1, 2, 3, ..., 9; in two-digits number 10, 11, ..., 99: for 1 there will be 10, 21, ..., 91 and the number of 1 will be 9; so there will be a simple conclusion:

- if n = 10, result will be 1 + 1(the second 1 is for the first digit);
- if n = 100, result will be 10 + 1(the second 1 is for the first digit);
- if n = 1000, result will be 100 + 1(the second 1 is for the first digit);

Simply, if n = 200, result will be 2*10 + 1(the second is for the first digit); if n = 300, result will be 3*10+1; if n = 400, result will be 4*10+1; ... , if n = 1000, result will be 10*10+1;

- then how about n = 230? take it apart to 200+30, 200 -> 2
*10+1(the second 1 is for the first digit), 30->3*1+1(the second 1 is for the first digit);

Now we've found the secret to dramatically reduce the time cost, traversing each digit instead of from 1 to n which will decrease the time complexity from O(n) to O(logn).

Equation for each unit will be (m is the unit: 1, 10, 100, 1000...) (n/m+8)/10*m+(n/m%10==1)*(n%m+1); Very complicated! Yuck! But let's try to take a closer look at this and have an example here to make it easy for you, suppose we have a number 1302193:

- if m==100, then n/m will be 13021, n%m will be 93; before the fixing hundred-1, there is 1302 which means when we are fixing 1 to hundred position there will be 0, 1, ..., 1301 can be selected before 1 and meantime the part after can be selected from 0, 1, 2, ..., 99 (100 choices can be used); why there is no 1302? we are considering unit 100 -> when hundred-1 fixed, the part after it is not enough for the unit 100 it's only 94 (from 0 to 93) which we will collect also; so the result for hundred-1 will be 1302*100+94;
- if m==1000, then n/m will be 1302, n%m will be 193; before thousand-2, there is 130 and according combination rules, there will (130+1)
*100 times occurrences of 1; why 130+1? 2 in thousand position, so fixing thousand 1 in thousand position and before thousand there can be 0-130 choices while after thousand there will be 0-999 -> just a unit 1000; clear? but the left 193 will be ignored unlike the previous situation while the thousand position has 2 instead of 1; so the final result for this unit is 131*1000; - if m==10000, then n/m will be 13, n%m will be 2193; quite similar, but since ten-thousand position has 0 instead of 2 or bigger digit, so there will be 0-12 choices only before ten-thousand instead of 0-13(unlike the previous example when m==1000 it's 0-130) and since it's not 1 so, the left part 2193 is also useless; so the final result for this unit is 13*10000;

At last, we reached each unit until n and sum them up, return it.

Bang. End of story!

- Space cost O(1)
- Time cost O(logn)

```
int countDigitOne(int n)
{
if(n < 10) return 0;
long long count = 0;
for(long long m = 1; m <= n; m *= 10)
{
int a = n/m;
int b = n%m;
count += (a+8)/10*m+(a%10==1)*(b+1); //0, 1 and >=2 should be treated differently when we are counting for each unit;
}
return count;
}
```