数字总和，直到得到一个作为输入的数字为止 [英] Sum of Digits till a number which is given as input

问题描述

如果输入数字，则找到直到该数字的所有数字的总和

If a number is given as an input find sum of all the digits of number till that number

例如输入11，则答案为1 + 2 .... + 9+(1 + 0)+(1 + 1) 蛮力法是计算小于一个数字的所有数字的总和.我已经实现了该方法，我想知道是否还有其他方法可以在不实际计算每个数字的总和

For example 11 is input then answer is 1+2....+9+(1+0)+(1+1) The Brute-force method would be to calculate sum of digits of all the numbers that are less than a number.I have implemented that method iam wondering if there is any other way to do it without actually calculating sum of digits of every number

推荐答案

您可以更快地执行此操作(在O(log n)操作中).设S(n)为所有数字0 <= k < n的数字总和.然后

You can do that faster (in O(log n) operations). Let S(n) be the sum of the digits of all numbers 0 <= k < n. Then

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

因为在小于10*n的数字​​中，每个k < n作为数字的起始部分出现10次，最后一位为0, 1, ..., 9.因此，最后一位数字的总和占45，而k位数的总和占10倍.

because among the numbers less than 10*n, each k < n appears as the initial part of a number 10 times, with last digits 0, 1, ..., 9. So that contributes 45 for the sum of the last digits, and 10 times the sum of the digits of k.

将其逆转，我们发现

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)的数字之和.

where DS(k) is the plain digit sum of k. The first two terms come from the above, the remaining two come from the sum of the digits of n - n%10, ..., n - n%10 + (n%10 + 1).

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

要包含上限，请将其命名为S(n+1).

To include the upper bound, call it as S(n+1).

这篇关于数字总和，直到得到一个作为输入的数字为止的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！