Leetcode258---Add Digits

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的数的各个位上的数字相加，若结果还大于0的话，则继续相加，直到数字小于10为止
。如果不看时间复杂度的话，直接按照字面解题用循环就可以。

public int addDigits(int num) {
        int result = num;
        while(result>=10){
            result=result/10+result%10;
        }
        return result;
    }

但是题目要求时间复杂度为O(1),所以肯定有个常数类型的公式来计算它。我们不妨列出一些数字和结果来找一下规律。
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
可以发现一个规律。这些数字每9个一循环，可以看作所有数都是对9取余(9的倍数除外)。这样写出代码如下

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

Leetcode258---Add Digits

推荐阅读更多精彩内容