Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Analysis:

fullCount(i): how many 1 there are for 0...10^i-1, e.g. fullCount(2) is the number of 1 in [0...99]

Now, we need count the 1s in n digit by digit. Using an eample, n=456, we count the 1s in [0...400] (for digit 4) + [0...50] (for digit 5) + [0...6] (for digit 6).

For digit 4, which belongs to 10^i where i=3, there are 4*fullCount(2), i.e., 1s in [0...99] for 000, 100, 200, 300, + the 100 1s on the current digit for [100...199].

We can use similar way to calculate digit 5 and digit 6.

If digit x > 1, then

digitCount(i,x) = x*fullCount(i-1) + 10^(i-1);

Specially, if digit x==1 then

digitCount(i,x) = 1* fullCount(i-1) + n%10^(i-1) + 1.

e.g., n=156, for digit 1, the count is fullCount(2) for [0...99] + (56+1) for [100...156].

On the other hand, fullCount(i) = 10*fullCount(i-1) + 10^(i-1),

which directly equals to i*10^(i-1).

Solution:

 1 public class Solution { 2     public int countDigitOne(int n) { 3         int iter = 0                                        ; 4         int fullCount = 0; 5         long power10 = 1; 6         int res = 0; 7         while (n >= power10) { 8             int digit = n / (int) power10 % 10; 9             int digitCount = 0;10             if (digit > 1) {11                 digitCount = digit * fullCount + (int) power10;12             } else if (digit == 1) {13                 digitCount = fullCount + n % (int) power10 + 1;14             }15             res += digitCount;16 17             // Get iter, power10, full count.18             // IMPORTANT: the sequence here is important!19             // because fullCount(i) = i * 10^(i-1).20             iter++;            21             fullCount = iter * (int) power10;22             power10 *= 10;23         }24         return res;25     }26 }

LeetCode-Number of Digit One