如何不使用列表计算1到极大数值范围内所有数字的总位数

你可以通过按位数分段计算的方法实现，完全不需要遍历所有数字，时间复杂度仅为O(log₁₀X)，即使X达到10¹⁸量级也能毫秒级返回结果，且不存在内存占用问题。

核心逻辑 #

• 1位数范围：1~9，共9个数字，总位数为 9*1
• 2位数范围：10~99，共90个数字，总位数为 90*2
• 3位数范围：100~999，共900个数字，总位数为 900*3
• n位数范围：10^(n-1)~10n -1，共 9*10^(n-1) 个数字，总位数为 9*10^(n-1)*n

计算时先累加所有小于X位数的区间总位数，再计算X所在位数区间的总位数，两者相加即为最终结果。

实现代码 #

def page_digits(pages):
    if pages == 0:
        return 0
    res = 0
    # 当前计算的位数
    digit = 1
    # 当前位数区间的起始值
    start = 1
    # 当前位数区间的结束值
    end = 9
    while end < pages:
        res += (end - start + 1) * digit
        digit += 1
        start *= 10
        end = end * 10 + 9
    # 加上最后一段不足完整区间的部分
    res += (pages - start + 1) * digit
    return res

验证示例 #

比如输入pages=123时：

1. 先累加1位数区间：9*1=9
2. 累加2位数区间：90*2=180，此时累计189
3. 最后计算3位数区间：123-100+1=24个，24*3=72，总结果189+72=261，和遍历计算结果一致。

内容的提问来源于stack exchange，提问作者KriSD