这是我的代码,但它要慢,任何方式更快地做到这一点..
我打的数字范围是123456789,但我不能低于15秒,我需要它低于5秒..
我打的数字范围是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)(11)(1 2)= 51.
我需要用公式而不是循环来做这个.
我在大约6秒内完成了大约15次测试.
并行我从15秒到4-8秒进行了一次测试..
只是为了向你展示我正在做的测试是很难的…
[Test]
public void When123456789_Then4366712385()
{
Assert.AreEqual(4366712385,TwistedSum.Solution(123456789));
}
在我的电脑上,我可以在5秒内完成所有测试.
看这个照片..
使用DineMartine答案我得到了以下结果：
解决方法
您的算法复杂度为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给出,我们正在寻找g在n上的递归表达式：
实际上g可以写成如下：
如果你找到h,问题就会得到解决.
