題目描述

給定非負整數 num，反覆將各位數字相加，直到結果為個位數。例如 38 → 3+8=11 → 1+1=2，返回 2。進階要求：無循環/遞歸，O(1) 時間複雜度。

解法一：模擬迭代（直觀易懂）

// Runtime: 2 ms
public class Solution {
    public int addDigits(int num) {
        int temp = 0;
        while (num > 9) {
            while (num != 0) {
                temp += num % 10;
                num /= 10;
            }
            num = temp;
            temp = 0;
        }
        return num;
    }
}

解法二：數學公式（數字根）

利用數字根性質：dr(n) = 1 + (n-1) % 9（n>0），dr(0)=0。推導來自同餘理論：10 ≡ 1 (mod 9)，故數字模 9 等於其各位數字和模 9。

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

注意：Java 中負數取模行為與數學定義不同，但 num ≥ 0 保證 num-1 ≥ -1，(num-1)%9 結果在 [-8, 8]，加 1 後在 [1, 9]，完全正確。

解法三：ceil 公式（等價變形）

// Runtime: 5 ms
public class Solution {
    public int addDigits(int num) {
        return (int)(num - 9 * Math.ceil((num - 1) / 9.0));
    }
}

複雜度對比

進階：Unicode / 大整數擴展

若輸入為大整數（字符串形式），可逐位累加取模 9，同樣 O(長度) 計算數字根。