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?

解法1:

class Solution(object):    def addDigits(self, num):        """        :type num: int        :rtype: int        """        # 1-9=1-9        # 10=1        # 11=2        # 12=3 ...        # 18=9        # 19=>1        # 20=>2        # 21=>3        # 99=>9        # 100=>1        # 101=>2        # 999=>9        def sum_digits(n):            ans = 0            while n:                ans += n%10                n /= 10            return ans                    ans = num        while ans > 9:            ans = sum_digits(ans)        return ans

观察发现是一个循环数组：

class Solution(object):    def addDigits(self, num):        """        :type num: int        :rtype: int        """        # 1-9=1-9        # 10=1        # 11=2        # 12=3 ...        # 18=9        # 19=>1        # 20=>2        # 21=>3        # 99=>9        # 100=>1        # 101=>2        # 999=>9        if num == 0: return 0        return 9 if num % 9 == 0 else num % 9