Leetcode 233. Number of Digit One

https://leetcode.com/problems/number-of-digit-one/

The key point is to get the law.

Solution:

# T:O(lgn) S:O(1)
class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        left = right = len = 1
        if n <= 0: return 0
        while n >= len:
            left = n / len
            right = n % len
            if left % 10 >= 2:
                res += (left / 10 + 1) * len
            elif left % 10 == 1:
                res += (left / 10) * len + (right + 1)
            else: res += (left / 10) * len
            len *= 10
        return res

Run Time: 44 ms