Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.
Example 1:
Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
Since 2 has only one digit, return it.
Example 2:
Input: num = 0
Output: 0
想法: 這題就是直接照著題目給的方式實作就好，問題是 follow up 要求用 O(1) 的時間來完成。
老實說 i have no idea，看了別人的作法原來是要用數學解阿! 原來題目描述的這個東西叫做 Digital root，我們可以用 num mod 9 來檢查 num 的 digital root 是多少。舉例而言 12345 可以拆解為:12345 = 1 x 10000 + 2 x 1000 + 3 x 100 + 4 x 10 + 5 = 1 x (9999 + 1) + 2 x (999 + 1) + 3 x (99 + 1) + 4 x (9 + 1) + 5= (1 x 9999 + 2 x 999 + 3 x 99 + 4 x 9) + (1 + 2 + 3 + 4 + 5) 可以看出前面的括弧可以被 9 整除，因此 12345 除以 9 的餘數就會來自後面的括弧剛好就是 digital root 的定義(所以位數相加且<10)所以 num 的 digital root 就會等於 num % 9 唯一的例外是 9，其實也不算是例外，只是說在 mod 9 中 9 剛好是等於 0的因此遇到 num % 9 == 0 時需要把結果替換成 9。
完整程式碼:解法一:class Solution {
public:
int addDigits(int num) {
int sum = num;
while (num >= 10) {
sum = 0;
while (num) {
sum += num % 10;
num = num / 10;
}
num = sum;
}
return sum;
}
};
解法二(數學解):class Solution {
public:
int addDigits(int num) {
if (num == 0) { return 0; }
if (num % 9 == 0) { return 9; }
return num % 9;
}
};
