342. Power of Four

Description

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

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

Example 1:

• Input: n = 16
• Output: true

Example 2:

• Input: n = 5
• Output: false

Example 3:

• Input: n = 1
• Output: true

Constraints:

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

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

Submitted Code

import numpy as np
import re

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

        # 10진법 -> 4진법
        base4 = np.base_repr(n, base=4)
        
        # 문자열 시작(^)은 1, 그 다음에 0이 0개 이상 존재, 그리고 문자열 종료($)
        return bool(re.match(r"^10*$", base4))  

import re

class Solution(object):
    def isPowerOfFour(self, n):
        if n <= 0:
            return False

        # 10진법 -> 4진법
        base4 = ''
        while n > 0:
            base4 = str(n % 4) + base4
            n //= 4
        
        # 문자열 시작(^)은 1, 그 다음에 0이 0개 이상 존재, 그리고 문자열 종료($)
        return bool(re.match(r"^10*$", base4))  

Runtime: 3 ms | Beats 14.30%
Memory: 12.34 MB | Beats 14.30%

n을 사진수로 변환한 뒤, 정규 표현식을 이용하여 4의 거듭제곱인 수만 찾아냈다. 파이썬에서는 십진수 → 사진수 로 변환하기 위헤 numpy를 쓰거나 루프를 사용해야 했다.

4⁰ = 1 → 1
4¹ = 4 → 10
4² = 16 → 100
4³ = 64 → 1000

Other Solutions

1st

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        if n <= 0:
            return False
            
        return math.log(n, 4).is_integer()

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

4의 거듭제곱은 이전에 풀었던 Power of three 문제와 같은 3의 거듭제곱에 비해 부동소수점 오차의 영향이 적기 때문에 이렇게 해도 통과될 수 있는 것 같다.

2nd

class Solution(object):
    def isPowerOfFour(self, n):
        if n <= 0:
            return False
        return (n & (n - 1)) == 0 and (n - 1) % 3 == 0

1. n & (n - 1) 연산으로 n이 2의 거듭제곱인지 확인 (231. Power of Two 참조)
2. (n - 1) % 3 == 0 연산으로 2의 거듭제곱 수 중 4의 거듭제곱만 필터링
   • n = 4^k = (2²)^k = 2^2k
   • n - 1 = 2^2k - 1 = (2^k - 1)(2^k + 1)
     • n - 1은 연속된 두 홀수의 곱이 됨(e.g. 3x5, 7x9)
     • 두 홀수는 항상 3의 배수를 포함하므로 n - 1이 3으로 나누어 떨어지면 4의 거듭제곱