卖萌的弱渣

I am stupid, I am hungry.

Number of Digit One

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

Example:

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

Hint:

Beware of overflow.

找规律

(Number-of-Digit-One.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = 1
        b = 1
        ret =0
        while n > 0:
            ret += (n+8)/10*a + (n%10 == 1) * b
            b += n%10 *a
            a *= 10
            n /= 10
        return ret