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

Question

我从亨利那里找到了答案

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

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

我的逻辑也将如下所示，上面的链接中也提到了

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 对于所有 p > 0 都可以被 9 整除。

因为 n = S1 + S0 并且 S1 可以被 9 整除，所以 S0 % 9 = n % 9。

这就是我们想要证明的

现在让 S(n) 表示返回数字 n 的数字总和的函数，然后正如我们刚刚观察到的那样

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

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

这就是提醒和数字总和的关系。