未分類

Add Digits

Go, LeetCode, Math

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)

分享到