e345 - Add Digits - 面試題

🔗 前往 ZeroJudge 原題

題目描述

題目要求給定一個非負整數 n，重複將其各位數字相加，直到結果為一個個位數。

解題思路

這道題可以透過不斷地將數字的各位數相加來實現，直到結果為個位數。然而，題目提示可以使用數學方法避免迴圈或遞迴。數位根 (digital root) 的概念可以幫助我們直接計算結果。數位根的計算公式為 dr(n) = (n - 1) % 9 + 1，其中 dr(n) 表示 n 的數位根。當 n 為 0 時，數位根為 0。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,n=0;
	while(cin >> a){
		n=0;
		while(1){
			n+=a%10;
			a/=10;
			if(a==0){
				if(n>=10){
					a=n;
					n=0;
					continue;
				}
				else{
					cout << n << "\n";
					break;
				}
			}
		}
	}
}