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
• Explanation: 27 = 3³

Example 2:

• Input: n = 0
• Output: false
• Explanation: There is no x where 3^x = 0.

Example 3:

• Input: n = -1
• Output: false
• Explanation: There is no x where 3^x = (-1).

Constraints:

• -2³¹ <= n <= 2³¹ - 1

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

Submitted Code

class Solution(object):
    def isPowerOfThree(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False

        while n % 3 == 0:
            n = n // 3
            
        return n == 1       # n이 1일 때만 True

Runtime: 8 ms | Beats 79.30%
Memory: 12.35 MB | Beats 83.48%

지난 문제 Power of Two의 경우 이진수에서 패턴이 있어서 비트 연산으로 쉽게 풀 수 있는데, 3의 거듭제곱은 패턴이 일정하지 않아서 같은 방법을 쓸 수 없었다.

Other Solutions

1st

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

time complexity: 𝑂(1)
space complexity: 𝑂(1)

재귀 호출이나 반복문 없이 수학적 성질을 이용할 수 있다. 32비트 정수 범위 내에서 가장 큰 3의 거듭제곱 수는 3¹⁹ = 1162261467인 것을 활용하는 것이다.

2nd

public boolean isPowerOfThree(int n) {
    return Integer.toString(n, 3).matches("10*");
}

3진수에서 3의 거듭제곱 수가 가진 규칙성(모두 1 다음에 0이 여러 개 있는 형태)을 활용한 방법이다. 10진수를 3진수 문자열로 변환한 뒤 정규 표현식을 이용하여 맞는 패턴인지 확인한다.

3⁰ = 1 → 1
3¹ = 3 → 10
3² = 9 → 100
3³ = 27 → 1000