[LeetCode] 258. Add Digits

轉自LeetCode

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?

<Solution>
解法一，就是按題目要求做

code 如下

	class Solution {
	public:
	int addDigits(int num) {
	while((num / 10) > 0) {
	int sum = 0;
	while(num) {
	sum += num % 10;
	num /= 10;
	}
	num = sum;
	}
	return num;
	}
	};

view raw addDigits_1.cpp hosted with ❤ by GitHub

那題目也問說，有沒有 O(1) 的解法

根據觀察

num    ans
 1      1
 2      2
 3      3
 4      4
 5      5
 6      6
 7      7
 8      8
 9      9
10      1
11      2
12      3
13      4
14      5
15      6
16      7
17      8
18      9
19      1
20      2

可以看出來，是每 9 個會循環，所以答案就會是 ans = (num - 1 ) % 9 + 1

code如下(參考資料)
c++

	class Solution {
	public:
	int addDigits(int num) {
	return (num - 1) % 9 + 1;
	}
	};

view raw addDigits_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun addDigits(num: Int): Int {
	var n = num
	var sum = 0
	while(n > 9) {
	sum = 0
	while(n > 0) {
	sum += n % 10
	n /= 10
	}
	n = sum
	}
	return n
	}
	}

view raw add_digits.kt hosted with ❤ by GitHub