<分区>
问题: 求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();