算法：数字和为个位数 -- 4种解法 258. Add Digits

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

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

Example 2:

Input: num = 0
Output: 0

Constraints:

0 <= num <= 231 - 1

1. 循环解法

class Solution {
    public int addDigits(int num) {
        if (num < 10) return num;
        while (num >= 10) {
            int sum = 0;
           while (num > 0) {
                sum += num % 10;
                num = num / 10;
            } 
            num = sum;
        }
        
        return num;
    }
}

2. 递归解法

class Solution {
    public int addDigits(int num) {
        if (num < 10) return num;
        return addDigits(addDigits(num / 10) + (num % 10));
    }
}

3. 余数9解法

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

解释：
I’ll try to explain the math behind this:

First you should understand:

10^k % 9 = 1
a*10^k % 9 = a % 9 

Then let’s use an example to help explain.

Say a number x = 23456

x = 2* 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6

2 * 10000 % 9 = 2 % 9

3 * 1000 % 9 = 3 % 9

4 * 100 % 9 = 4 % 9

5 * 10 % 9 = 5 % 9

Then x % 9 = ( 2+ 3 + 4 + 5 + 6) % 9, note that x = 2* 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6

So we have 23456 % 9 = (2 + 3 + 4 + 5 + 6) % 9

4. 余数9 一行代码解法

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

Explain, take 438 as an example

4.1 [Step 1]:

438  == 40*10 +3*10 +8 ;

4+3+8 == 4*(10%9)(10%9)+3(10%9)+8%9= 15 ;

4.2 [Step 2]:

15  == 1*10 + 5 ;
 
1+5 == 1*(10%9)+5%9= 6 ;

4.3 [So we can see]:

ab%9%9%9==ab%9; 

just return num%9; and don't forget num==0 or num==9   

参考

https://leetcode.com/problems/add-digits/discuss/?currentPage=1&orderBy=most_votes&query=