未分類

Power of Three

Go, LeetCode, Math

Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up:

Could you do it without using any loop / recursion?

提示 解題應用
Math 腦力激盪

Default:

1
2
3
func isPowerOfThree(n int) bool {
}

解答思路:

先前曾經寫過類似的題目Power of Two，不過這邊看半天對於3的n次方數位元實在沒有什麼特別之處，follow up又希望你一樣能不用任何的迴圈及遞回，想了辦天也沒什麼辦法，只好去看其它人的討論，與其說是解題，倒不如說是腦力激盪，如果兩個同樣都是3的n次方數，比較大的那個去向比較小的取餘數必為0，就是運用這樣的概念，找一個3的n次方在32位元內極大值，可以發現是3的19次方1162261467，題目會帶入的值鐵定小於等於其極大值，透過這樣的小訣竅最後就可以很快速的找出解。

程式碼解說:

非常單純的短短幾行，首先判斷n是否大於等於0，接著用算好的3次方在32位元內的極大值(1162261467)對n取餘數，若為0表示同為3的n次方回傳true，其它的狀況則回傳false

1
2
3
4
if n > 0 && 1162261467%n == 0 {
	return true
}
return false

完整程式碼:

1
2
3
4
5
6
func isPowerOfThree(n int) bool {
	if n > 0 && 1162261467%n == 0 {
		return true
	}
	return false
}

總結:

相較於2的n次方是用位元的方法來判斷，3的n次方甚至是其它數的次方則可以用整除的方法來判斷，不過前提是要先知道取得帶入值型別是幾位元，且算出對應位元該相同數次方的極大值，最後用極大值對其帶入的數取餘數，若為0表示同為該數的n次方，此方法相對麻煩在於需事先算出極大值。

分享到