gpt4 book ai didi

algorithm - 求1到N所有数字的位数之和

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:59:43 25 4
gpt4 key购买 nike

<分区>

问题:求1到N(包括两端)所有数字的位数之和

时间复杂度应该是 O(logN)

对于 N = 10,总和为 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

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

这个递归 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)):

    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();

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com