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:

  1. Beware of overflow.

不解释了，看引用的文章吧

1
2
3
4
5
6
public int countDigitOne(int n) {
    int ones = 0;
    for (long m = 1; m <= n; m *= 10)
        ones += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
    return ones;
}

Ref:

  1. http://bookshadow.com/weblog/2015/07/08/leetcode-number-digit-one/
  2. http://www.cnblogs.com/grandyang/p/4629032.html
  3. https://discuss.leetcode.com/topic/18054/4-lines-o-log-n-c-java-python