algorithm - 数字总和直到作为输入给出的数字

Question

如果给定一个数字作为输入，找到该数字的所有数字的总和，直到该数字

例如输入 11 那么答案是 1+2....+9+(1+0)+(1+1)蛮力方法将计算所有小于数字的数字的总和。我已经实现了该方法，我想知道是否有任何其他方法可以做到这一点而无需实际计算每个数字的数字总和

Answer 1

你可以更快地做到这一点(在 O(log n) 操作中)。让S(n)是所有数字的数字之和0 <= k < n .然后

S(10*n) = 10*S(n) + 45*n

因为在数字中小于10*n , 每个 k < n作为数字的初始部分出现 10 次，最后的数字为 0, 1, ..., 9 .所以这对最后一位数字的总和贡献了 45，并且是 k 的数字总和的 10 倍.

反过来，我们发现

S(n) = 10*S(n/10) + 45*(n/10) + (n%10)*DS(n/10) + (n%10)*((n%10)-1)/2

哪里DS(k)是 k 的纯数字总和.前两项来自上面，其余两项来自n - n%10, ..., n - n%10 + (n%10 + 1)的数字之和.

开始是 S(n) = 0对于 n <= 1 .

要包括上限，将其称为 S(n+1) .