Description：

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.

Follow up:

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

题意很简单，最容易想到的办法就是循环迭代，如果是<10的就返回。下面是一种递归的方法。

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

　　那么怎么做才能不用递归和循环迭代来把复杂度降到O(1)呢，这让我联想到了公式。来通过数据找找规律。

前30个数据测试：

public static void main(String[] args) {		for(int i=0; i<30; i++) {			System.out.println(i + " " + addDigits(i));		}	}

　　

0 0

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

21 3

22 4

23 5

24 6

25 7

26 8

27 9

28 1

29 2

找出来规律了吧。

其实是这样的：(num-1) % 9 + 1

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