解題說明
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這個公式成立嗎?(提示:同餘理論) - 如果要求不能使用除法和模運算,該如何求解?
- 此概念能否擴展到其他進位制(例如十六進位)?