題目

難度：★★☆☆☆
類型：數(shù)學(xué)

給定一個非負(fù)整數(shù) num，反復(fù)將各個位上的數(shù)字相加，直到結(jié)果為一位數(shù)。

進(jìn)階:
你可以不使用循環(huán)或者遞歸，且在 O(1) 時間復(fù)雜度內(nèi)解決這個問題嗎？

示例

輸入: 38
輸出: 2
解釋: 各位相加的過程為：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位數(shù)，所以返回 2。

解答

方案1：循環(huán)判斷

這道題目和【題目202. 快樂數(shù)】很像，流程相同，我們首先考慮循環(huán)方式實(shí)現(xiàn)：

1. 我們首先定義一個函數(shù)get_bit_sum，用于求取一個整數(shù)的各位和；

2. 循環(huán)執(zhí)行求取各位和的過程，直到結(jié)果為一位數(shù)。

class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """

        def get_bit_sum(n):
            s = 0
            while n:
                r, n = n % 10, n // 10
                s += r
            return s

        while num > 9:
            num = get_bit_sum(num)

        return num

方案2：找規(guī)律

假設(shè)一個整數(shù)為m=a+b10+c100+...，那么這個整數(shù)求取各位和后得到n=a+b+c+...，前后之間的差值為m-n=b*9 + c *99 + ...，可以很容易看出，差值是9的整數(shù)倍，因此輸入m除以9后得到的余數(shù)即為我們需要的數(shù)（為什么？），如果輸入恰好是9的整數(shù)倍，則直接返回9（為什么？）。

class Solution(object):
    def addDigits(self, num):
        """
        和快樂數(shù)很像
        :type num: int
        :rtype: int
        """

        if num > 9:
            num %= 9
            if num == 0:
                return 9

        return num

如有疑問或建議，歡迎評論區(qū)留言~