自然数的数根

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

示例:

输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
进阶:
你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-digits

解答1：（暴力解法）

class Solution:
    def addDigits(self, num: int) -> int:
        sum = 0
        while len(str(num)) > 1:
            for i in str(num):
                sum += int(i)
            num = sum
            sum = 0
        return num
​原理：不断求该数的数字和直到数字和为个位数

解答2：（高级解法）

class Solution:
    def addDigits(self, num: int) -> int:
        return (num - 1) % 9 + 1

找规律：

在数学中，数根(又称位数根或数字根Digital root)是自然数的一种性质，换句话说，每个自然数都有一个数根。

数根是将一正整数的各个位数相加（即横向相加），若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于十为止[1]，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。

例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。

数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。

数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。

另外，数根也可以用来判断数字的整除性，如果数根能被3或9整除，则原来的数也能被3或9整除。

​
​我们先来找一下规律
原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3 

我们不难发现该数的数根就是(num - 1) % 9 + 1的结果（%为求余符号）

证明：

我们以12345这个五位数举例，那么有：

12345 = 1 * 9999 + 2 * 999 + 3 * 99 + 4 * 9 + (1 + 2 + 3 + 4 +5)

设m % 9 = a ， n % 9 = b（m, n, a, b是自然数）

则m = 9 * x + a，n = 9 * y + b

所以(m + n) % 9 = m % 9 + n % 9

则可证明：12345 % 9 =  (1 +2 +3 +4 +5) % 9 = 15 % 9 = (1 + 5) % 9 = 6

所以可得:一个数与它的数根同模于9

又自然数n的数根恒小于10大于0

所以自然数n的数根就是(n -1) % 9 + 1

Q.E.D