计算十进制自然数区间总位数的最优算法是什么？

核心采用前缀和思想：先实现一个辅助函数count_digits_up_to(n)计算从1到n所有自然数的总位数，那么区间[start, end]的总位数直接等于count_digits_up_to(end) - count_digits_up_to(start - 1)即可。该方案时间复杂度为常数级O(1)（仅和数字的最大位数相关，64位自然数最多循环20次），是理论上的复杂度最优解，远优于朴素遍历的O(N)复杂度。

核心计算公式 #

对于d位自然数n：

• 1位数（1~9）总位数：9 * 1
• 2位数（10~99）总位数：90 * 2
• 3位数（100~999）总位数：900 * 3
• k位数通用总位数：9 * 10^(k-1) * k
• 累加前d-1位的总位数后，加上最后d位段的总位数：(n - 10^(d-1) + 1) * d

优化后的Rust实现 #

fn count_digits_up_to(n: usize) -> usize {
    if n == 0 {
        return 0;
    }
    let mut total = 0;
    let mut digits = 1;
    let mut start = 1; // 当前位数的起始值，依次为1、10、100……
    let mut end = 9; // 当前位数的结束值，依次为9、99、999……
    while end < n {
        total += (end - start + 1) * digits;
        digits += 1;
        start *= 10;
        end = end * 10 + 9;
    }
    // 补上最后不足整段的位数部分
    total + (n - start + 1) * digits
}

fn range_digits(start: usize, end: usize) -> usize {
    assert!(start <= end && start >= 1);
    count_digits_up_to(end) - count_digits_up_to(start - 1)
}

方案优势 #

1. 完全规避了原实现中浮点转整数的精度问题，不会出现大数场景下位数计算错误的问题
2. 无unwrap调用，不会触发运行时panic，鲁棒性更强
3. 逻辑更简洁易懂，无需处理中间多位数段的复杂拆分逻辑，前缀和思路更易维护
4. 性能和原优化方案同属常数级，已经达到理论最优下限，不存在计算效率更高的解法

测试验证 #

输入start=5、end=20005时：

• count_digits_up_to(20005)结果为88919
• count_digits_up_to(4)结果为4
• 最终输出88919 - 4 = 88915，和预期结果完全一致。

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