231. Power of Two

Description

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

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

Example 1:

• Input: n = 1
• Output: true
• Explanation: 2⁰ = 1

Example 2:

• Input: n = 16
• Output: true
• Explanation: 2⁴ = 16

Example 3:

• Input: n = 3
• Output: false

Constraints:

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

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

Submitted Code

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n <= 0:
            return False
        epsilon = 1e-12
        log_val = math.log(n, 2)
        return abs(round(log_val) - log_val) < epsilon

Runtime: 0 ms | Beats 100.00%
Memory: 12.50 MB | Beats 10.39%

처음에는 n = 2^x 이기 때문에 이를 x = log₂n 으로 변경한 뒤, .is_integer() 함수로 x가 정수인지 확인하는 방법을 사용했다. 하지만 n이 2의 거듭제곱임에도 부동소수점 오차때문에 x가 실수로 계산되는 케이스가 있었다. 이 경우 x를 정수로 반올림한 값과 실제 x값의 차이가 충분히 작다면 오차를 허용하는 방법을 사용할 수 있다. 엡실론 값을 1e-9로 했을 때는 n = 2147483647일 때 실패했고, 1e-12까지 정밀도를 높였을 때 모든 케이스를 통과했다.

Other Solutions

1st

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0

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

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        cnt = bin(n).count('1')
        return cnt == 1

time complexity: 𝑂(𝑘) ← 𝑘(n의 비트 수) = log₂𝑛
space complexity: 𝑂(𝑘)

비트 연산 방식이 더 빠르고 오차없이 정확하기 때문에 좋은 것 같다. 활용된 원리는 2의 거듭제곱 수는 이진수에서 딱 하나의 비트만 1이라는 것이다. 첫 번째 코드는 n과 n-1의 AND 연산 결과가 0일 경우 True를 반환하는 것이고, 두 번째 코드는 n을 2진수 문자열로 변환한 뒤 1의 개수가 1일 때만 True를 반환한다.

n = 8 (1000)

n     (8) = 1000 
n - 1 (7) = 0111
----------------
↓
n & (n-1) = 0000