[LeetCode] 258 Add Digits | 计算树根

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?

思路

最初看到这个题目，觉得迭代加法取余的方式肯定是最low的，分析规律。

  • 最终得到个位数，结果取值范围[0,9]
  • 各位数累加的计算规律：dr(10)=10-9=1, dr(11)=11-9=2
  • 但并不是对九取余的关系，因为mod(n, 9)的取值范围时[0, 8]
  • 可以抽象为dr(n)=mod(n-1,9) + 1

时间复杂度：O(1), 空间复杂度O(1)

  • 各位数累加的计算规律：12345=1x(9999+1)+2x(999+1)+3x(99+1)+4x(9+1)+5=(1x9999+2x999+3x99+4x9)+(1+2+3+4+5)

    源码

    1
    2
    3
    4
    5
    6
    7
    8
    int addDigits(int num) {
        if(num==0)
            return 0;
        int res = (num-1)%9+1;
        //int res = num - (num-1)/9*9;//wikipedia-digital root
        return res;
        
    }

运行结果：

1101 / 1101 test cases passed.
Status: Accepted
Runtime: 8 ms
Submitted: 0 minutes ago
You are here! Your runtime beats 2.85% of csubmissions.

总结

  1. 专业的数学称呼叫树根，或数字根(Digital Root)
  2. 树根的特性1：两数字的和的数根等于两数字分别的数根的和。
  3. 树根的特性2：数根也可用来判断数字的整除性，如数根能被3或9整除，则原来的数也能被3或9整除。

参考文献