Problem statement

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

Solution

For number $a_1,\dots, a_k$ all numbers less than it can be divided into groups: $a_1, \dots a_{k-1} b_k$, where $b_k < a_k$, $a_1,\dots a_{k-2} b_{k-1} c_k$, where $b_{k-1} < a_{k-1}$ and $c_k$ is any number and so on: $a_1, \dots, a_l b_{l+1} c_{l+2} \dots c_k$.

Complexity

For each group we can evaluate number of ones inside in O(1). So, we have overall complexity O(k).

Code

class Solution:
    def f(self, d, l):
        if d == 0:
            return 0
        if d == 1:
            return 10**(l-1) * l
        if d >= 2:
            return 10**(l-1)*l*d + 10**l
        
    def countDigitOne(self, n):
        if n <= 0:
            return 0
        Out, NumOnes = 0, 0
        str_n = str(n)
        k = len(str_n)
        for i in range(k):
            dig = int(str_n[i])
            rest = k - i - 1
            Out += (self.f(dig, rest) + NumOnes * dig * (10 ** rest))
            if dig == 1:
                NumOnes += 1
            
        return int(Out) + NumOnes