d442 - 10591 - Happy Number

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷給定的正整數是否為 Happy Number。Happy Number 的定義是，經過迭代計算每個數字的平方和，最終能得到 1。如果無法得到 1，則該數為 Unhappy Number。

解題思路

本題的核心思想是利用雜湊表（Hash Table）來檢測是否出現循環。對於每個輸入數字，我們計算其平方和，並將結果存入雜湊表中。如果計算過程中出現重複的數字，則說明存在循環，該數為 Unhappy Number。如果最終計算結果為 1，則該數為 Happy Number。

複雜度分析

• 時間複雜度: O(n)，其中 n 是計算平方和的迭代次數。在最壞情況下，n 可能很大，但由於雜湊表的查找操作是常數時間，因此整體時間複雜度仍然可以視為 O(n)。
• 空間複雜度: O(n)，用於存儲雜湊表中的數字。在最壞情況下，雜湊表可能需要存儲所有計算過程中出現的數字。

程式碼

#include <stdio.h>
int main(){
	int b,c=1;
	scanf("%d",&b);
	while(scanf("%d",&b)>0){
		printf("Case #%d: %d is ",c,b);
		c++;
		int a[1001]={0},s=0;
		bool ans=0;
		if(b<=1000)
			a[b]++;
		while(a[1]==0){
			a[s]++;
			if(a[s]>1){
				ans=1;
				break;
			}
			s=0;
			while(b>0){
				s+=(b%10)*(b%10);
				b/=10;
			}
			b=s;
		}	
		(ans==0)?printf("a Happy number.\n"):printf("an Unhappy number.\n");
	}
}