Question:

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.

Hint:

Beware of overflow.

Thinking:

This is question to find formula. We should notice that:

1                   1                                                                                     [1, 9]

11                 10  11  12  13  14  15  16  17  18  19                              [10, 19]

1                   21                                                                                   [20, 29]

1                   31                                                                                   [30, 39]

1                   41                                                                                   [40, 49]

1                   51                                                                                   [50, 59]

1                   61                                                                                   [60, 69]

1                   71                                                                                   [70, 79]

1                   81                                                                                   [80, 89]

1                   91                                                                                   [90, 99]

11                 100  101  102  103  104  105  106  107  108  109          [100, 109]

21                 110  111  112  113  114  115  116  117  118  119             [110, 119]

11                 120  121  122  123  124  125  126  127  128  129          [120, 129]

We should divide it into three situations in every digit division: one is bigger than 2, another is equal to 1 and the rest is less than 0.

Solution:

public int countDigitOne(int n) {
    int res = 0;
    for (long m = 1; m <= n; m*=10) {
        res += (n/m + 8) / 10 * m + (n/m % 10 == 1? n%m+1:0);
    }
    return res;
}

Reference: https://leetcode.com/discuss/44281/4-lines-o-log-n-c-java-python