326. Power of Three

LeetCode 326. Power of Three

Description

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3^x.

Example 1:

Input: n = 27
Output: true

Example 2:

Input: n = 0
Output: false

Example 3:

Input: n = 9
Output: true

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

Tags

Math

Solution

The largest n in interger-wise who is the power of 3 is 3^19 = 1162261467, and its factors are only 3^x where x ranges from 0 to 19. Thus, we only need to test if 3^19%n == 0.

Complexity

• Time complexity: $O(1)$

• Space complexity: $O(1)$

Code

func isPowerOfThree(n int) bool {
	return n > 0 && 1162261467%n == 0 // 3^19 < 2^31 - 1
}

Reference

1. 3 的幂