LeetCode 258：Add Digits（各位相加 / 數字根）

一、題目描述

給定非負整數 num，反覆將各位數字相加，直到結果為一位數。要求 O(1) 時間、無循環/遞歸。

範例： 38 → 3+8=11 → 1+1=2 → 返回 2。

二、解題思路：數字根公式

這是經典的「數字根」問題。對於十進制，數字根公式為：

dr(n) = 0                    (n == 0)
dr(n) = 9                    (n % 9 == 0 && n != 0)
dr(n) = n % 9                (otherwise)

等價於：1 + (n - 1) % 9（對 n>0）。

原理：10 ≡ 1 (mod 9)，故數字各位權重模 9 均為 1，數字模 9 等於各位和模 9。

三、代碼實現（C++）

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

四、複雜度分析

• 時間複雜度：O(1)
• 空間複雜度：O(1)

本題考察數學洞察力，掌握數字根公式可秒殺。