LeetCode 258. Add Digits [Easy] [C++] 解題筆記

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;
    }
};