导航
导航
文章目录
  1. 题目
  2. 翻译

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?

翻译

给出一个非负整数num,反复叠加其各位直到结果只有一位为止。
例如:
给出num=38,过程如下:3+8=11,1+1=2。因为2只有一位,返回。
追加:
能否给出不用任何循环或递归的O(1)运行时间的算法?

最直接的思路,按照题中给出的过程,逐步计算,返回结果:

1
2
3
4
5
6
7
8
9
10
11
// 递归
public int addDigits(int num) {
if (num < 10)
return num;
int sum = 0;
while (num != 0) {
sum += num % 10;
num /= 10;
}
return addDigits(sum);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 非递归
public int addDigits(int num) {
while (num >= 10)
num = getSum(num);
return num;
}

public int getSum(int num) {
int sum = 0;
while (num != 0) {
sum += num % 10;
num /= 10;
}
return sum;
}

但题中给出了追加问题,能否在O(1)时间内解出?
并给出了四个提示:
1.A naive implementation of the above process is trivial. Could you come up with other methods?
2.What are all the possible results?
3.How do they occur, periodically or randomly?
4.You may find this Wikipedia article useful.(https://en.wikipedia.org/wiki/Digital_root)

翻译如下:
1.简单地实现上述计算过程是很普通的,你能想出其他办法么?
2.都有哪些可能结果?
3.它们是周期性地还是随机地出现?
4.这篇维基百科文章可能会有所帮助。(https://en.wikipedia.org/wiki/Digital_root)

从中我们可以得知:
Result = 1 + ( ( num - 1 ) mod 9 )

算法如下:

1
2
3
public int addDigits(int num) {
return 1 + (num - 1) % 9;
}

运行时间均为2ms