Math

今天寫到 leetcode 258. Add Digits (https://leetcode.com/problems/add-digits/)，發現了這個有趣的題目。題目本身不難，但是 follow up 要求寫出 O(1) 時間複雜度的解法，因此卡了一下。 看到 wiki (https://en.wikipedia.org/wiki/Digital_root#Congruence_formula) 才發現這樣的問題被叫做 Digital Root，而且還可以在不同進位下討論，挺有趣的。 先看一個簡單的範例： 有一個 5 進位 的數字 14324 （這是用 5 進位表示），把這個數字的每一位相加然後用 5 進位表示，直到剩下一位，這個數字會是多少？ 1 + 4 + 3 + 2 + 4 = 14（10 進位） = 24（5 進位） 2 + 4 = 6（10 進位） = 11（5 進位） 1 + 1 = 2（5 進位） 這個數字會是 2。但是計算很麻煩，因爲要在 5 進位上面做運算，是人類很不收悉的進位。 簡單的方法就是把所有的計算都換到 10 進位上面。 有小標的 5 就是指這個數字是 5 進位的。 ...