Digital Root 的黑魔法
Digital Root 或者 Digital Sum 是针对非负 int 类型的操作，给定一个 num：
- 如果 0 <= num <= 9，即当前只有一位数字，那么返回这个数字
- 如果 num >= 10，即不止一位数字，那么把各位数字加起来得到新的数字，重复这个过程，直到新的数字只有一位。比如输入 12345:
- 1 + 2 + 3 + 4 + 5 -> 15
- 1 + 5 -> 6
- 最终返回 6
直觉上说，应该属于 Simulation，可以按照给定的方式计算：
1class Solution:
2 def addDigits(self, num: int) -> int:
3 if 0 <= num <= 9:
4 return num
5 else:
6 return self.addDigits(sum(int(d) for d in str(num)))
但是有另外一种方法，可以只用 O(1) 的时间：
- 如果 0 <= num <= 9，直接返回 num
- 如果 num % 9 结果是 0，返回 9，否则返回余数
1class Solution:
2 def addDigits(self, num: int) -> int:
3 if 0 <= num <= 9:
4 return num
5 else:
6 m = num % 9
7 return m if m else 9
例如 12345 % 9 = 6，可以直接返回 9。下面是证明的过程：
-
10^n 与 1 对 9 同模，可以专业地表示为： $$ 10^{n}\equiv 1\pmod{9} $$
-
那么可以得到
α * 10^n与 α 对 9 同模： $$ \alpha \times 10^{n} \equiv \alpha \pmod{9} $$ -
经过一次 digital sum 操作，输入数字与输出数字，仍然对 9 同模： $$ \alpha _{1} \times 10^{n-1} + \alpha _{2}\times 10^{n-2}+\cdots \cdots + \alpha _{n-1} \times 10^{1}+\alpha _{n} \times 10^{0} \equiv \alpha _{1} + \alpha _{2} + \cdots \cdots + \alpha _{n-1}+\alpha _{n} \pmod{ 9} $$
最后返回的值，是对 9 的模，因为每次变化的同模等效关系，即可直接返回原数字对 9 的模。
这种技巧平时读到会觉得挺有意思，不过作为面试题的 follow up，感觉意义不大了。因为并不太可能当场想出来，只能证明对方是不是知道这个结论。
参考抄袭链接：