解題說明
Add Digits
題目描述：給定一個非負整數 num，反覆將其各位數字相加，直到結果為一位數為止。回傳該一位數。
解題思路：這個問題的本質是「數字根（Digital Root）」。數學上可以證明，任何正整數的數字根等於 1 + (num - 1) % 9。原因是 10 ≡ 1 (mod 9)，因此任何數字模 9 後的餘數等於其各位數字之和模 9 的餘數。特殊處理 num = 0 的情況即可。這個公式讓我們在 O(1) 時間內得出答案。
C++ 解法
複雜度分析
時間複雜度：O(1) — 僅需一次模運算。
空間複雜度：O(1) — 僅使用常數空間。
虛擬碼
1. If num == 0, return 0 2. Return 1 + (num - 1) % 9
其他解法
模擬法 O(log num)：直接按題意模擬，反覆計算各位數字之和直到結果為一位數。外層迴圈最多跑 O(log log num) 次，每次內層計算位數和為 O(log num)。簡單直觀但效率不如數學公式。
遞迴法：每次遞迴計算一輪位數之和，base case 為 num < 10。與模擬法本質相同，但寫法更簡潔。
延伸思考
- 你能解釋為什麼
1 + (num - 1) % 9這個公式成立嗎？（提示：同餘理論） - 如果要求不能使用除法和模運算，該如何求解？
- 此概念能否擴展到其他進位制（例如十六進位）？