(LeetCode) 326. Power of Three

326. Point of Three

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Math
• 난이도 : Easy

Problem

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

Solution (Iterator)

Exapnder

class Solution {
    fun isPowerOfThree(n: Int): Boolean {
        var num = n
        while (num % 3 == 0) {
            num /= 3
        }
        return num == 1
    }
}

Solution (Recursive)

Exapnder

class Solution {
    fun isPowerOfThree(n: Int): Boolean {
        return when (n) {
            0 -> false
            1 -> true
            else -> n % 3 == 0 && isPowerOfThree(n / 3)
        }
    }
}

Solution (Mathematics)

Exapnder

class Solution {
    fun isPowerOfThree(n: Int): Boolean {
        if (n == 0) {
            return false
        }

        var number = n.toDouble()

        return number == Math.pow(
            3.0,
            Math.round(
                (Math.log(number) / Math.log(3.0))
            ).toDouble()
        )
    }
}

Point of Thinking

• Iterator로 풀면 타임아웃이 발생했다.
• Recursive로는 Accepted.
• 분류가 Math이니만큼 수학 공식을 적용해서도 풀이해보았다.
  • 3^x뿐만 아니라 대부분문의 Power of 시리즈에도 적용이 가능한 공식이다.

어떤 수 n이 x의 거듭제곱인 경우

$log_x(n)$

위의 결과값은 정수임을 이용하는 것이다.

위의 공식은 아래와 같이 변환할 수 있다.

$log_x(n) = \frac{log_k(n)}{log_k(x)}$

이를 코드로 변환하면

Math.log(n) / Math.log(x)

로 표현할 수 있고 이 문제에 적용하면

Math.log(n) / Math.log(3.0)

이 된다.

위 결과값은 거듭제곱의 경우 정수이므로, Math.round()를 통해 보정을 해주고 Math.pow()를 통해 3^(결과값)이 주어진 n과 동일하다면 true, 아니면 false로 판별할 수 있다.