将一个给定数字的所有位相加直到数字最后只剩下一位的算法

Question

原题：

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

看了一下别人的时间复杂度 O(1) 的解法：

public class Solution {
    public int addDigits(int num) {
        return num==0?0:(num%9==0?9:(num%9));
    }
}

我的理解大致如下：

假设一个数字为 abcd，那么：

(a + b + c + d) % 9
= (999a + 99b + 9*c + a + b + c + d) % 9
= abcd % 9

而 (a + b + c + d) 得到的一个数，我们假设为 n，那么

abcd % 9
= n % 9;

而 n 可以递归到直到最后只剩下一位数字，假设这个数字为 k，那么就有

result = (k % 9 == 0) ? 9 : (k % 9);

也就是说，数字 abcd 可以转化为：

result = (num == 0) ? 0 : ((num % 9 == 0) ? 9 : (num % 9));

但是总感觉理解上有一些奇怪，也不知道有没有错误，求各位大神能给出一个较为清晰的算法正确性证明。

Answer 1

你的证明是正确的。但是再梳理一下，反过来描述可能更容易理解。

假设n>0，按照题目要求的计算步骤最后得到的结果为k，那么当且仅当k==9时k%9=0，其他情况下k%9=k。

而任何数x与它的各位数字之和y之间都满足x%9==y%9，这个结论在你的证明中已经很明确了，理解起来应该没有问题。

所以应用该结论可以得到n%9==k%9，当该结果为0时k==9，否则k==n%9。

上面是n>0的情况，当n==0时，结果当然为0。