找出从1到N的所有数字的数字总和 [英] Find the sum of the digits of all the numbers from 1 to N

问题描述

问题: 找到从1到N(包括两端)的所有数字的数字总和

时间复杂度应为O(logN)

如果N = 10，则总和为1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 +(1 + 0)= 46

For N = 10 the sum is 1+2+3+4+5+6+7+8+9+(1+0) = 46

对于N = 11，总和为1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 +(1 + 0)+(1 + 1)= 48

For N = 11 the sum is 1+2+3+4+5+6+7+8+9+(1+0)+(1+1) = 48

对于N = 12，总和为1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 +(1 + 0)+(1 + 1)+(1 + 2)= 51

For N = 12 the sum is 1+2+3+4+5+6+7+8+9+(1+0)+(1+1) +(1+2)= 51

此递归解决方案就像是一种魅力，但我想了解达成这种解决方案的理由.我相信它是基于有限归纳法的，但是有人可以确切说明如何解决这个问题吗?

This recursive solution works like a charm, but I'd like to understand the rationale for reaching such a solution. I believe it's based on finite induction, but can someone show exactly how to solve this problem?

我已经粘贴(稍作修改)了上述解决方案:

I've pasted (with minor modifications) the aforementioned solution:

static long Solution(long n)
{
    if (n <= 0)
        return 0;
    if (n < 10)
        return (n * (n + 1)) / 2; // sum of arithmetic progression
    long x = long.Parse(n.ToString().Substring(0, 1)); // first digit
    long y = long.Parse(n.ToString().Substring(1)); // remaining digits
    int power = (int)Math.Pow(10, n.ToString().Length - 1);

    // how to reach this recursive solution?
    return (power * Solution(x - 1))
    + (x * (y + 1)) 
    + (x * Solution(power - 1)) 
    + Solution(y);
}

单元测试(不是O(logN)):

Unit test (which is NOT O(logN)):

    long count = 0;
    for (int i=1; i<=N; i++)
    {
        foreach (var c in i.ToString().ToCharArray())
            count += int.Parse(c.ToString());
    }

或者:

Enumerable.Range(1, N).SelectMany(
    n => n.ToString().ToCharArray().Select(
        c => int.Parse(c.ToString())
    )
).Sum();

推荐答案

这实际上是一个O(n^log10(2))时间解决方案(log10(2)大约是0.3).不知道这是否重要.我们有n = xy，在这里我使用级联来表示级联，而不是乘法.这是下面有注释的四个关键行.

This is actually a O(n^log10(2))-time solution (log10(2) is approximately 0.3). Not sure if that matters. We have n = xy, where I use concatenation to denote concatenation, not multiplication. Here are the four key lines with commentary underneath.

return (power * Solution(x - 1))

计算从1包括在内的数字到x*power排除的数字在x位置的贡献.此递归调用不会增加复杂性，因为它会在固定时间内返回.

This counts the contribution of the x place for the numbers from 1 inclusive to x*power exclusive. This recursive call doesn't contribute to the complexity because it returns in constant time.

+ (x * (y + 1))

这计算了x位在从x*power(含)到n(含)之间的贡献.

This counts the contribution of the x place for the numbers from x*power inclusive to n inclusive.

+ (x * Solution(power - 1))

计算从1含(含)到x*power互斥的编号的低位位置的贡献.此呼叫的电话号码比n短一位.

This counts the contribution of the lower-order places for the numbers from 1 inclusive to x*power exclusive. This call is on a number one digit shorter than n.

+ Solution(y);

计算从x*power(含)到n(含)的数字的低阶位的贡献.此呼叫的电话号码比n短一位.

This counts the contribution of the lower-order places for the numbers from x*power inclusive to n inclusive. This call is on a number one digit shorter than n.

我们应用主定理的情况1得到时间限制.为了将运行时间降低到O(log n)，我们可以解析地计算Solution(power - 1).我不记得是什么封闭形式了.

We get the time bound from applying Case 1 of the Master Theorem. To get the running time down to O(log n), we can compute Solution(power - 1) analytically. I don't remember offhand what the closed form is.

这篇关于找出从1到N的所有数字的数字总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！