LeetCode (2) - Power of three (파이썬, python)

❓ 문제

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

Example 4:

Input: n = 45
Output: false

Constraints:

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

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

---

Given Code

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        

---

접근법 1

3의 제곱으로 나타낼 수 있는 수인지 판별하는 문제입니다.

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while True:
            if n % 3 == 0:
                n = n // 3
            else:
                return False
            if n == 1:
                break
        return True

3으로 나눠지는지 확인하는 루프를 짜서 푼 코드입니다.

---

접근법 2-1

근데 문제 말미에 Follow up: Could you solve it without loops/recursion? 이 있네요? 그래서 pow 함수를 이용했습니다.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        return n > 0 and pow(3, 31, n) == 0

pow()는 인자를 두개 혹은 세개를 받을 수 있습니다.

pow(a, b) -> a**b

pow(a, b, c) -> (a**b)% c

인데 속도는 더 빠르다고 하네요. 2의 31승보다 n의 절대값이 작다는 조건이 있으니 return n > 0 and pow(3, 31, n) == 0 와 같은 조건문으로 판별할 수 있습니다.

---

접근법 2-2

pow의 두번째 인자에 대한 고찰입니다. 저 값이 꼭 31일 필요는 없는게 pow(3, b, n) 의 경우에 2^31보다 3^b가 크기만 하면 되거든요. \(3^b > 2^{31}\\ blog3 > 31log2\\ b > 31log2 / log3\) 두등식을 만족하는 가장 작은 정수 b은 20이네요. 그래서 최종 코드는 다음과 같이 제출했습니다.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        return n > 0 and pow(3, 20, n) == 0