258. Add Digits

Leetcode Math

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

Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

Follow up:

• Could you do it without any loop/recursion in $O(1)$ runtime?

分析

这道题目考查的是对于数字的基本操作。每次从数字中取出最低一位，累加的总和不能超过10.

public int addDigits(int num) {
    int digit = 0, n = 0;
    while (num > 9) {
        n = 0;
        while (num > 0) {
            digit = num % 10;
            n += digit;
            num /= 10;
        }
        num = n;
    }
    return num;
}

但follow up 里又说了： 你能不使用任何循环/递归在$O(1)$ 时间内解决吗？实际上这是一个有名的数根问题，解决这个问题有一个[Congruence formula](

$$\operatorname{dr}(n) = \begin{cases}0 & \mbox{if}\ n = 0, \\ 9 & \mbox{if}\ n \neq 0,\ n\ \equiv 0\pmod{9},\\ n\ {\rm mod}\ 9 & \mbox{if}\ n \not\equiv 0\pmod{9}\end{cases}$$

$$\text{或者:} \mbox{dr}(n) = 1\ +\ ((n-1)\ {\rm mod}\ 9)$$

为了了解这个公式我们先来观察1到20的所有的树根：

1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8    
9    9    
10    1
11    2
12    3    
13    4
14    5
15    6
16    7
17    8
18    9
19    1
20    2

根据上面的列举，我们可以得出规律，每9个一循环，所有大于9的数的树根都是对9取余，那么对于等于9的数对9取余就是0了，为了得到其本身，而且同样也要对大于9的数适用，就用$(n-1)%9+1$这个表达式来包括所有的情况。

int addDigits(int num) {
    return (num - 1) % 9 + 1;
}