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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 13
<strong>Output:</strong> 6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

"""
12345, pos 0: 5, pos 1: 4 etc.

0..9 - 1 time 
00..99 - pos 1: 10 times, pos 0: 10 times
000..999 - pos 2: 100 times, pos 1: 100 times, pos 2: 100 times

0000..2345 - pos 3: 1000, pos 2: 3 * 100, pos 1: 24 * 10, pos 4: 235
0000..2106 - pos 3: 1000, pos 2: 2 * 100 + 7, pos 1: 20 * 10, pos 0: 209


pos(n, k) - number of apperances of 1 in position k for integers <=n
d(n, k) = (n // (10 ** k) % 10) k-th digit of n
pref(n, k) = (n // (10 ** (k + 1)) - integer prefix befor position k
suff(n, k) = n % (10 ** k) - integer suffix after position k

d(k) in [2..9]:
    # Consider all possible prefix values so that integer <=n, including zeros
    # Suffix value can be arbitrary because digin in position k guarantees that number <=n
    pos(n, k) = (pref(n, k) + 1) * (10 ** k)

d(k) == 1:
    pos(n, k) = pref(n, k) * (10 ** k) + suff(n, k) + 1

d(k) == 0:
    pos(n, k) = pref(n, k) * (10 ** k)

 pref(n, k) * (10 ** k) - baseline number of options for all values
 d(k) == 1: adding suff(n, k) + 1 options
 d(k) > 1: adding 10 ** k options

"""

def ans_for_pos(n: int, k: int):
    power_ten = 10 ** k
    digit = (n // power_ten) % 10
    answer = (n // (power_ten * 10)) * power_ten
    if digit == 1:
        answer += n % power_ten + 1
    elif digit >= 2:
        answer += power_ten

    return answer


class Solution:
    def countDigitOne(self, n: int) -> int:
        answer = 0
        for k in range(len(str(n))):
            answer += ans_for_pos(n, k)

        return answer
16600