LeetCode 258. 各位相加：數學規律與 O(1) 解法

LeetCode 258. 各位相加

題目描述

給定非負整數 num，反覆將各位數字相加，直到結果為個位數。

範例

num = 38 → 3+8=11 → 1+1=2 → 返回 2。

數學規律：數字根

該過程實際計算的是**數字根**。對於十進制數，數字根與模 9 運算直接相關：

• 若 num == 0，結果為 0。
• 若 num % 9 == 0 且 num > 0，結果為 9。
• 否則結果為 num % 9。

統一公式：1 + (num - 1) % 9（需處理 num=0 特例）。

代碼實現

int addDigits(int num) {
    if (num == 0) return 0;
    if (num % 9 == 0) return 9;
    return num % 9;
}

證明概要

十進制數 num = a_k*10^k + ... + a_1*10 + a_0。
因 10 ≡ 1 (mod 9)，故 10^i ≡ 1 (mod 9)。
所以 num ≡ a_k + ... + a_1 + a_0 (mod 9)。
各位相加不改變模 9 餘數，最終個位數結果即為模 9 餘數（0 映射為 9）。

複雜度分析

• 時間複雜度：O(1)，無循環遞歸。
• 空間複雜度：O(1)。

總結

各位相加問題本質是求數字根，利用模 9 同餘性質可 O(1) 直接計算，是數學規律在算法優化中完美應用的典型案例。