当给出n的位数之和时,求出n + 1,n + 2 ......的位数之和

Question

我们可以很容易地计算给定数字的数字之和,但是我们可以使用任何数学公式或模式来确定下一个数字的总和而不必一次又一次地对所有数字求和吗？

例如

Sum of 1234 = 1+2+3+4 = 10
Sum of 1235 = 1+2+3+5 = 11
Sum of 1236 = 1+2+3+6 = 12

我可以在这里看到某种模式,但无法提出任何有效的数学算法.

我使用下面的方法来计算数字的总和:

public int sum(long n) {  
    int sum = 0;   
    while (n != 0) {    
        sum += n % 10;
        n /= 10;  
    }  
    return sum;  
}

哪个工作正常,但它是CPU密集型的.我想更快地做到这一点.如果我有一系列数字,说10->19我只需要计算10的数字,然后为每个数字添加一个,直到19.

如果我已经有以前数字的总和,有没有有效的方法来计算数字的总和？

Answer 1

DigitSum(n+1) = DigitSum(n) + 1 - (9 * NumberOfEndingZeros(n+1))

如果你不想找到t连续数字的数字,而是找到t连续数字(n + 1,n + 2,...,n + t)的数字之和,那就更简单了.

Sum(DigitSum(i)) for i = n+1 to n+t = a(n+t) - a(n)

其中a(i)是整数序列百科全书中的A037123序列,它有几个公式.我认为这会很快:

a(n) = (1/2) * ( (n+1) * (n - 18 * sum{k>0, floor(n/10^k)} )
               + 9 * sum{k>0, (1+floor(n/10^k))*floor(n/10^k)*10^k}
               )

Answer 2

最快的方法是提取每个数字并随时添加.

public static void main(String... args) {
    // check values
    int runs = 1000000;
    for (int i = 100; i < runs; i++) {
        int sum = sumDigits(i - 1);
        int sum1 = sumDigits(i);
        int sum2 = sumDigits(sum, i);
        if (sum1 != sum2) throw new AssertionError(i + ": " + sum1 + " != " + sum2);
    }
    long start = System.nanoTime();
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(i);
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time = System.nanoTime() - start;
    System.out.printf("sumDigits took an average of %,d ns%n", time / runs);
    long start2 = System.nanoTime();
    int lastSum = 0;
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(lastSum, i);
        lastSum = sum;
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time2 = System.nanoTime() - start2;
    System.out.printf("sumDigits using previous value took an average of %,d ns%n", time2 / runs);

    long large = Long.MAX_VALUE - runs - 1;

    long start3 = System.nanoTime();
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(large + i);
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time3 = System.nanoTime() - start3;
    System.out.printf("sumDigits took an average of %,d ns%n", time3 / runs);
    long start4 = System.nanoTime();
    int lastSum2 = sumDigits(large);
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(lastSum2, large + i);
        lastSum2 = sum;
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time4 = System.nanoTime() - start4;
    System.out.printf("sumDigits using previous value took an average of %,d ns%n", time4 / runs);

}

public static int sumDigits(long n) {
    int sum = 0;
    do {
        sum += n % 10;
        n /= 10;
    } while (n > 0);
    return sum;
}

public static int sumDigits(int prevSum, long n) {
    while (n > 0 && n % 10 == 0) {
        prevSum -= 9;
        n /= 10;
    }
    return prevSum + 1;
}

版画

sumDigits took an average of 32 ns
sumDigits using previous value took an average of 10 ns
sumDigits took an average of 79 ns
sumDigits using previous value took an average of 7 ns

对于较大的值,它可以节省大约70 ns.它为您的代码增加了一些复杂性.你必须使用第一个sumDigit来引导总和,因为你无法从1到10 ^ 18一直计算.