class Solution:
    def countDigitOne(self, n: int) -> int:
        #let m number of digits of n
        #TC: O(m)
        #SC: O(m)
        #For explanation, see Guan Huifeng 
        #https://www.youtube.com/watch?v=uB7DfQul6GU

        S = str(n)[::-1]

        res = 0

        for i in range(len(S)):
            left = n // (10**(i+1))
            res = res + left*(10**i)

            if int(S[i]) > 1:
                res = res + 10**i
            elif int(S[i]) == 1:
                right = n % (10**i) + 1
                res = res + right

        return res