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

Example:


Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Difficulty: interview

Starter code:

class Solution:
    def countDigitOne(self, n: int) -> int:
        

Solutions:
class Solution:
     def countDigitOne(self, n):
         """
         :type n: int
         :rtype: int
         """
         ones, m = 0, 1
         while m <= n:
             ones += (n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1)
             m *= 10
         return ones

class Solution:
     def countDigitOne(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n <= 0:
             return 0
         q, x, ans = n, 1, 0
         while q > 0:
             digit = q % 10
             q = q // 10
             ans += q * x
             if digit == 1:
                 ans += n % x + 1
             elif digit > 1:
                 ans += x
             x *= 10
         return ans

class Solution:
        def countDigitOne(self, n):
             ones, wei = 0,  1
             while wei <= n:
                 m = int(n / wei) % 10  # 求某位数字
 
                 if m > 1:
                     ones += (int(n / wei / 10) + 1) * wei
                 elif m == 1:
                     ones += (int(n / wei / 10)) * wei + (n % wei) + 1
                 else:
                     ones += (int(n / wei / 10)) * wei
                 wei *= 10
             return int(ones)

class Solution:
     def countDigitOne(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n <= 0:
             return 0
         one, m = 0, 1
         while m <= n:
             one += (n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1)
             m *= 10
         return one

class Solution:
     def countDigitOne(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n <= 0:
             return 0
         counts, length, digits = 0, len(str(n)), [int(i) for i in str(n)]
         counts = digits[0] * (length - 1) * (10 ** (length - 2)) + min(digits[0] - 1, 1) * (10 ** (length - 1)) + \
                  max(2 - digits[0], 0) * (n - 10 ** (length - 1) + 1) + Solution().countDigitOne(n - digits[0] * \
                  (10 ** (length - 1)))
         return int(counts)

class Solution:
     def countDigitOne(self, n):
         """
         :type n: int
         :rtype: int
         """
         # 特殊判断
         if n <= 0:
             return 0
         # 先得到输入数字n的位数
         i = 0
         while pow(10, i) <= n:
             i += 1
         if i == 1:
             return 1
         
         # 递归得到1～s之间所有的1值
         s = n % pow(10, i - 1)
         temp = self.countDigitOne(s)
         
         # 再得到s+1～n之间所有的1值
         # 先得到最高位为1的所有1值
         t = n // pow(10, i - 1)
         if t > 1:
             temp1 = pow(10, i - 1)
         elif t == 1:
             temp1 = s + 1
         # 再得到其它位为1的所有1值
         temp2 = t * (i - 1) * pow(10, i - 2)
         return temp + temp1 +temp2