未分類

Add Digits

Add Digits

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

For example:

1
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?

提示 解題應用
Math 公式

Default:

1
2
3
func addDigits(num int) int {
}

解答思路:

一般看到題目我想就直接用迴圈不斷去取餘數,將這些結果做總合再去判斷是否剩一個數字(除10商不為0),如此一來便能快整寫出如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func addDigits(num int) int {
var remainder int
sum := num
for sum/10 != 0 {
num = sum
sum = 0
for num != 0 {
remainder = num % 10
sum = sum + remainder
num = num / 10
}
}
return sum
}

不過注意到follow up,希望你可以不用任何的迴圈及遞回完成,除非先前就已經知道,否則要慢慢推出結論有一定的難度在,這邊就遵循 Digital Root 所給的公式直接套入即可解決。

程式碼解說:

基本上就是套入上述所給予的公式: dr(n) = 1 + ((n-1) mod 9)

完整程式碼:

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

總結:

要找出一數字的Digital Root除了能用迴圈及遞回完成之外,如果有下述公式來結論的話便能在O(1)的複雜度完成。

dr(n) = 1 + ((n-1) mod 9)

分享到