# -*- coding:utf-8 -*-
# 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
# 为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,
# 但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,
# 可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。


class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # ones记录1出现的个数
        # m记录1的位置处于那一位

        # 分三种情况讨论：
        # 1、当m表示百位，且百位数 > 1 ，如n = 31456，m = 100，则a = 314，b = 56，
        # 此时百位为1的次数有a // 10 + 1 = 32（最高两位0~31），
        # 每一次都包含100个连续的点（100 - 199），
        # 共有(a // 10 + 1) * 100

        # 2、当m表示百位，且百位数 = 1，如n = 31156，m = 100，则a = 311，b = 56，
        # 此时百位对应的就是1，则共有a / 10（最高两位0-30）次是包含100个连续点，
        # 当最高两位为31（即a = 311），本次只对应局部点00~56，共b + 1次，
        # 共有(a // 10 * 100) + (b + 1)

        # 3、当m表示百位，且百位对应的数为0，如n = 31056，i = 100，则a = 310，b = 56，
        # 此时百位为1的次数有a // 10 = 31（最高两位0~30）

        # 当a > 1时，(a // 10 + 1) = (a + 8) // 10
        # 当a = 0，1时，a // 10 = (a + 8) // 10

        ones, m = 0, 1
        while m <= n:
            a, b = n // m, n % m
            ones += (a + 8) // 10 * m + (a % 10 == 1) * (b + 1)
            m *= 10
        return ones


if __name__ == '__main__':
    S = Solution()
    print(S.NumberOf1Between1AndN_Solution(256))

