得到n下面每个数字的总和

Question

这是我的代码,但是速度慢,任何方式都可以更快地完成..我正在打的数字范围是123456789但我不能低于15秒,我需要它低于5秒..

long num = 0;

for (long i = 0; i <= n; i++)
{
    num = num + GetSumOfDigits(i);
}

static long GetSumOfDigits(long n)
{
    long num2 = 0;
    long num3 = n;
    long r = 0;
    while (num3 != 0)
    {
        r = num3 % 10;
        num3 = num3 / 10;
        num2 = num2 + r;
    }

    return num2;
}

sum =(n(n+1))/2 没有给我我需要的结果,没有正确计算..

对于N = 12,总和是1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 +(1 + 0)+(1 + 1)+(1 + 2)= 51.我需要这样做用公式代替循环..

我在大约6秒内完成了大约15次测试.

并行我从15秒到4-8秒进行了一次测试..

只是为了向你展示我正在做的测试是很难的...

[Test]
public void When123456789_Then4366712385()
{
   Assert.AreEqual(4366712385, TwistedSum.Solution(123456789));
}

在我的电脑上,我可以在5秒内完成所有测试..看看照片..

有了DineMartine答案我得到了这些结果:

Answer 1

有点令人费解但是时间缩短到几乎为零:

    private static long getSumOfSumOfDigitsBelow(long num)
    {
        if (num == 0)
            return 0;
        // 1 -> 1 ; 12 -> 10; 123 -> 100; 321 -> 100, ...
        int pow10 = (int)Math.Pow(10, Math.Floor(Math.Log10(num)));
        long firstDigit = num / pow10;
        long sum = 0;
        var sum999 = getSumOfSumOfDigitsBelow(pow10 - 1);
        var sumRest = getSumOfSumOfDigitsBelow(num % pow10);
        sum += (firstDigit - 1)*(firstDigit - 0)/2*pow10 + firstDigit*sum999;
        sum += firstDigit*(num%pow10 + 1) + sumRest;
        return sum;
    }


    getSumOfSumOfDigitsBelow(123456789) -> 4366712385 (80us)
    getSumOfSumOfDigitsBelow(9223372036854775807) -> 6885105964130132360 (500us - unverified)

诀窍是避免一次又一次地计算相同的答案.例如33:

你的方法:

sum = 1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2)+ ... +(3+2)+(3+3)

我的方法:

sum = 10*(0 + (1+2+3+4+5+6+7+8+9)) + 
   10*(1 + (1+2+3+4+5+6+7+8+9)) + 
   10*(2 + (1+2+3+4+5+6+7+8+9)) + 
   3*(3 + (1 + 2 + 3))

该(1+2+3+4+5+6+7+8+9)双组分必须只计算一次.-trick 0..firstDigit-1可以避免循环n(n-1)/2.我希望这是有道理的.

复杂性是O(2^N)N计算位数.这看起来非常糟糕,但即使是长期最大,也足够快到5秒的阈值.有可能O(n)通过getSumOfSumOfDigitsBelow()仅调用一次来运行该算法,但看起来会更复杂.

优化的第一步:看看你的算法;)

在DineMartine的回答之后回到这个问题:

为了进一步优化算法,sum999可以用显式公式替换-part.让我们9999...9=10^k-1在代码中取一些数字并相应地替换:

sum(10^k-1) = (9 - 1)*(9 - 0)/2*pow10 + 9*sum999 + 9*(num%pow10 + 1) + sumRest
sum(10^k-1) = 36*pow10 + 9*sum999 + 9*(num%pow10 + 1) + sumRest

sum999并且sumRest类型数量相同10^k:

sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*(num%pow10 + 1)
sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*((10^k-1)%pow10 + 1)
sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*pow10
sum(10^k-1) = 45*pow10 + 10*sum(10^(k-1)-1)

我们有一个定义sum(10^k-1)和知道sum(9)=45.我们得到:

sum(10^k-1) = 45*k*10^k

更新的代码:

    private static long getSumOfSumOfDigitsBelow(long num)
    {
        if (num == 0)
            return 0;
        long N = (int) Math.Floor(Math.Log10(num));
        int pow10 = (int)Math.Pow(10, N);
        long firstDigit = num / pow10;
        long sum = (firstDigit - 1)*firstDigit/2*pow10 
            + firstDigit* 45 * N * pow10 / 10 
            + firstDigit*(num%pow10 + 1) 
            + getSumOfSumOfDigitsBelow(num % pow10);
        return sum;
    }

这是与DineMartine相同的算法,但是以递归方式表示(我比较了两种实现,是的,我确定它是;)).运行时间几乎为零,时间复杂度是O(N)计算位数或O(long(N))取值.

Answer 2

你的算法复杂度是N log(N).我找到了一个更复杂的算法log(N).我们的想法是迭代数字位数:

log10(n) = ln(n)/ln(10) = O(log(n)).

该算法的演示涉及许多组合演算.所以我选择不在这里写.

这是代码:

public static long Resolve(long input)
{
    var n = (long)Math.Log10(input);
    var tenPow = (long)Math.Pow(10, n);
    var rest = input;
    var result = 0L;
    for (; n > 0; n--)
    {
        var dn = rest / tenPow;
        rest = rest - dn * tenPow;
        tenPow = tenPow / 10;
        result += dn * (rest + 1) + dn * 45 * n * tenPow + dn * (dn-1) * tenPow * 5 ;
    }

    result += rest * (rest + 1) / 2;

    return result;
}

现在你可以在几分之一秒内解决问题.

想法是将输入写为数字列表:

假设解决方案由函数f给出,我们正在寻找f在n上的ga递归表达式:

实际上g可以写成如下:

如果你找到h,问题就会得到解决.