326. Power of Three #

Problem #

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

Example 1:

Input: 27
Output: true

Example 2:

Input: 0
Output: false

Example 3:

Input: 9
Output: true

Example 4:

Input: 45
Output: false

Follow up:

Could you do it without using any loop / recursion?

Problem Summary #

Given an integer, write a function to determine whether it is a power of 3.

Solution Ideas #

Determine whether a number is 3 to the power of n.
The simplest idea for this problem is to use a loop, which can pass. But the problem asks to determine it without loops, so number theory knowledge is needed. Since 3^20 exceeds the range of int, 3^19 is the largest value of this form in the int type. This problem uses the same idea as Problem 231.

Code #


package leetcode

// Solution 1 Number theory
func isPowerOfThree(n int) bool {
	// 1162261467 is 3^19,  3^20 is bigger than int
	return n > 0 && (1162261467%n == 0)
}

// Solution 2 Lookup table method
func isPowerOfThree1(n int) bool {
	// 1162261467 is 3^19,  3^20 is bigger than int
	allPowerOfThreeMap := map[int]int{1: 1, 3: 3, 9: 9, 27: 27, 81: 81, 243: 243, 729: 729, 2187: 2187, 6561: 6561, 19683: 19683, 59049: 59049, 177147: 177147, 531441: 531441, 1594323: 1594323, 4782969: 4782969, 14348907: 14348907, 43046721: 43046721, 129140163: 129140163, 387420489: 387420489, 1162261467: 1162261467}
	_, ok := allPowerOfThreeMap[n]
	return ok
}

// Solution 3 Loop
func isPowerOfThree2(num int) bool {
	for num >= 3 {
		if num%3 == 0 {
			num = num / 3
		} else {
			return false
		}
	}
	return num == 1
}