所有数字的总和，直到它变成 java 中的单个数字，复杂度为 o(1)？

Question

我从 Henry

那里找到了答案

int sum = n % 9;
if (sum == 0) sum = 9;

这里

java program that sums up the digits of a number until it is a single number Eg: 2748303 = 2+7+4+8+3+0+3 = 27 = 2+7 = 9

谁能解释一下相加和余数之间的关系？

我的逻辑也应该是下面的，上面也提到了link

int sum = 0;
    while (n > 9 ) {
                 sum=0;
        while (n > 0) {
            int rem;
            rem = n % 10;
            sum = sum + rem;
            n = n / 10;
        }
        n = sum;
    }

但是 2 行答案很棒。

Answer 1

在 Java 中，整数的范围有限，因此进行提醒具有 O(1) 渐近复杂度。

现在回答你的主要问题：

Can any one please explain how adding digits and remainder are related?

首先注意任何数字n除以9与其数字之和相同的提示。如果这看起来不是很明显，这里有一个证明草图。

证明

设 nk,...,n2,n1,n0 为数字 n 的 k+1 位。

令 10^p 表示 10 的 p 次方。

然后

n = 10^k * nk + ... + 100 * n2 + 10 * n1 + n0 =
  = (10^k - 1) * nk + ... + (100-1) * n2 + (10-1) * n1 +
    + nk + ... + n2 + n1 + n0

现在注意最后一行是数字的数字总和n

  S0 = nk + ... + n2 + n1 + n0

让

 S1 = (10^k - 1) * nk + ... + (100-1) * n2 + (10-1) * n1

可以被 9 整除因为 10^p - 1 = 9...9 可以被 9 整除所有 p > 0.

因为n = S1 + S0且S1能被9整除，所以S0 % 9 = n % 9.

这就是我们想要证明的

现在让S(n)表示函数returns数位总和n，那么正如我们刚才观察到的

  n % 9 = S(n) % 9 = S(S(n)) % 9 = ...

我们可以继续处理，直到达到一位数。

这就是提醒和位数的关系。

所有数字的总和，直到它变成 java 中的单个数字，复杂度为 o(1)？

Sum of all the digits till it becomes single digit in java with o(1) complexity?

java

complexity-theory

logic