LeetCode258 Add Digits

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

样例

1
2
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. 
Since 2 has only one digit, return it.

思路

给一个非负数,每次将其替换为它的各位数字之和,直到为这个数只有一位为止。(其实就是求一个数的digital root)

直接模拟显然是可以的,那么考虑如何$\mathcal{O}(1)$算出答案。

对任意一个数 $n$ 来说,可以将其表示为

$n = a{n-1} \ast 10^{n-1} + a{n-2} \ast 10^{n-2} + … a{1} \ast 10^{1} + a{0} \ast 10^{0}$

同时注意到,10的任意次方模9都为1,则

$ n \equiv a{n-1} \ast 1 + a{n-2} \ast 1 + … a{1} \ast 1 + a{0} \ast 1 (mod 9) $

右边就是$n$的各位数之和,然后把它赋给$n$不断迭代即可。

结论:

digital root

代码

1
2
3
4
5
6
7
8
class Solution {
public:
int addDigits(int num) {
if (num == 0) return 0;
int ans = num % 9;
return ans ? ans : 9;
}
};
分享到 评论