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
8int 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.
总结
- 专业的数学称呼叫树根，或数字根(Digital Root)
- 树根的特性1：
两数字的和的数根等于两数字分别的数根的和。 - 树根的特性2：
数根也可用来判断数字的整除性，如数根能被3或9整除，则原来的数也能被3或9整除。