所有数字的总和，直到它在java中成为具有o（1）复杂度的单个数字？

Question

我从亨利那里找到了答案

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

这里

java程序，将数字的数字相加直到它是单个数字 例如：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)渐近复杂度。

现在回答你的主要问题：

任何人都可以解释添加数字和余数之间的关系吗？

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

证明

让nk,...,n2,n1,n0是k+1数字的数字n。

让我们10^p表示p10的-th 次方。

然后

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)表示返回数字的数字总和的函数n，然后正如我们刚刚观察到的

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

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

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