目录

1. 题目描述

2. 解题分析

2.1 递归法

2.2 数学方法

3. 代码实现

1. 题目描述

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

示例 1:
输入: num = 38
输出: 2 
解释: 各位相加的过程为：
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数，所以返回 2。

示例 2:
输入: num = 0
输出: 0
 
提示：0 <= num <= 2**31 - 1
 
进阶：你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

2.1 递归法

        逐位相加，如果结果小于10就返回；否则就针对结果再执行逐位相加；。。。直到最终得到的结果小于10返回。这是典型的递归法的思路。

        时间复杂度：对于 num 计算一次各位相加需要 的时间。需要几次递归调用能够结束呢。由于0 <= num <= 2**31 - 1=2147483647，所以最大为10位数，且最高位不大于2，所以第一轮各位相加最大可能结果为92，最多还需要两次，所以最大递归调用次数为3次。所以总的时间复杂度仍为 。

        空间复杂度：O(1)。存储结果的digitsum以及递归调用的开销均为常数。

2.2 数学方法

        对于给定的自然数，反复将各个位上的数字相加，直到结果为一位数，该一位数被称为原自然数的数根。数根又称数字根（Digital root），是自然数的一种性质，很显然每个自然数都有唯一一个数根。利用自然数的性质，则能在 O(1) 的时间内计算数根。

        设num为n位数，从高位到低位的数字分别记为a0, a1,...,a(n-1)，则可以得到：

        由于(10**i-1)必定是9的倍数，所以，num的各数位之和与num自身是模9同余的，记为：

        进一步，num_digitsum各数位之和也是与num_digitsum同余的。。。所以，任意自然数num的数根就等于num模9运算的结果？且慢，当num=9时，数根是9而不是0！原因在于要返回的值是10以内，而不是模9运算结果范围的9以内。所以这里还需要进一步的区分讨论，如下所示：

• 当num 不是 9 的倍数时，其数根即为num模9运算结果。
• 当num 是 9 的倍数时：
•         如果 num=0，则其数根是 0；
•         如果 num>0，则各位相加的结果大于 0，其数根也大于 0，因此其数根是 9。

3. 代码实现

import time
class Solution:
    def addDigits(self, num: int) -> int:
        # print('addDigits({0})'.format(num))
        if num < 10:
            return num
        else:
            digitsum = 0
            while num > 0:
                digitsum += num%10
                num = num // 10
            if digitsum < 10:
                return digitsum
            else:
                return self.addDigits(digitsum)

if __name__ == '__main__':        
    
    sln = Solution()  

    num = 38
    tStart = time.time()        
    ans = sln.addDigits(num)
    tElapsed = time.time() - tStart            
    print('input={0}, ans={1}, tCost={2:3.2f}(sec)'.format(num,ans,tElapsed))

本系列总目录：

笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889