e284 - 放暑假了!!!!!

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷輸入的整數是否為 2 的乘冪。如果是，輸出 "Yes"，否則輸出 "No"。

解題思路

程式碼預先計算了 2 的 0 到 31 次方，並將其儲存在 a 陣列中。對於每個輸入的數字 b，程式碼迭代 a 陣列，檢查 b 是否等於 a 陣列中的任何一個元素。如果找到相等的元素，則輸出 "Yes" 並結束迭代。如果 b 大於 a 陣列中的所有元素，則輸出 "No"。

複雜度分析

• 時間複雜度: O(32) = O(1)。因為陣列大小固定為 32，所以迭代次數是常數。
• 空間複雜度: O(32) = O(1)。程式碼使用了一個大小為 32 的陣列來儲存 2 的乘冪，空間使用是常數。

程式碼

#include <stdio.h>
int main(){
	long long int a[32],b=1,i=0;
	for(i=0;i<32;i++,b*=2)
		a[i]=b;	
	while(scanf("%lld",&b)>0){
		for(i=0;i<32;i++){
			if(a[i]>b){
				printf("No\n");
				break;
			}
			else if(a[i]==b){
				printf("Yes\n");
				break;
			}
		}
	}
}