233. Number of Digit One

A cycle is 0~9 for one position. 1 appears a certain number of times in each cycle.

For example, given number 32107.

At position 7, 1 appears 3210 complete cycles, and within each cycle 1 appears once. Also, because 7 > 1, so it can be regarded as one more complete cycle. In total 1 appears 3211 times at position 7.

At position 0, 1 appears 321 complete cycles, and within each cycle 1 appears 10 times, eg, ...10-...19. In total 1 appears 321 * 10 times at position 0.

At position 1, 32 complete cycles, and within each cycle 1 appears 100 times, eg, ..100-..199. Notice here it is 1, so it has incomplete cycle from 32100-32107, which is 32107 % 100 + 1 = 8 times. In total 1 appears 32 * 100 + 8 times at position 1.

So on so forth.

A generalized code for any digit 0 ~ 9 is below.
对于一个位置来说，可能出现的数字时0-9，这是一个cycle
对于32107来说，对于7所在的位置，因为7>1，所以可能出现的数字是00001-32101.共3211
对于0所在的位置，因为0<1，所以可能出现的数字是0001-3201，对于每一个cycle，有10-19这些数字，所以最后是32010
对于1所在的位置因为1 = 1，所以有001-321这些数字，对于每一个cycle，有100-199，但是对于321后面只有32100-32107，所以共有32100 + 1 * 8
以此类推
代码如下：

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 1:
            return 0
        result = 0
        # number of appearances for one cycle when 1 appears at position i
        i = 1
        while n >= i:
            # complete cycle, one more complete cycle if current digit > 1
            cycle = n / (i * 10) + (1 if n / i % 10 > 1 else 0)
            result += cycle * i
            # incomplete cycle if current digit == 1
            if n / i % 10 == 1:
                result += n % i + 1
            i *= 10
        return result