e345: Add Digits - 面試題

內容

給一個正整數 n，將所有位數相加總和，如果總和不是個位數，重複相加步驟直到總和為個位數。

e.g. 345 => 3 + 4 + 5 = 12，12 => 1 + 2 = 3

疑？？怎麼覺得好像很眼熟？？好像寫過？？

那你知道如何不用 Loop/Recursion 來算出解答嗎？

輸入

每一行有一個數字 n，0 <= n <= 2147483647

EOF 結束

0
123
456

輸出

輸出該數字對應到的解答

0
6
6

解題思路

數學題，題目說不用迴圈或遞迴也能解代表有一定的規律，所以先列出前面幾項

然後就會由於相加和超過 9 時，會再觸發一次相加直到和變成個位數，而這個動作會讓數的最終合保持在 “1~9” 9 個數字做循環，所以可以用和 9 取餘來表示其規律。

但因為 9 和 9 取餘是 0 ，而題目要求的是 9，所以先將原數減去一取餘完再加回來變成

ans = (n-1) % 9 + 1

來處理數字為 9 的倍數時的例外情況，但這時候又產生另一個問題，當 n 為 0 時會變成 -1 和 9 取餘，所以在取餘前先判斷是否為 0 變成

ans = n != 0 ? (n - 1) % 9 + 1 : 0

然後每次都按公式輸出答案即可，另外在 C 中 -1 % 9 得到的解會是 -1，再加上 1 之後剛好會變回 0，所以不做判斷也可以，只是感覺不太好。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

int main()
{
    int n;
    while (scanf(" %d", &n) == 1)
    {
        printf("%d\n", n ? (n - 1) % 9 + 1 : 0);
    }
    return 0;
}