LeetCode 231. Power of Two

Description

https://leetcode.com/problems/power-of-two/

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 == 2x.

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

Example 4:

Input: n = 4
Output: true

Example 5:

Input: n = 5
Output: false

Constraints:

  • -231 <= n <= 231 - 1

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

Explanation

Create a function to find the power of a number. And use the function to check if a power of 2 can be found.

Python Solution

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        
        for i in range(0, n + 1):
            if self.power(2, i) == n:
                return True
            elif self.power(2, i) > n:
                return False

        return False
        
        
    def power(self, a, b):
        if b == 0:
            return 1
        
        if b == 1:
            return a
        
        if b % 2 == 0:
            return self.power(a * a, b // 2)
        else:
            return self.power(a * a, b // 2) * a
            
  • Time Complexity: O(NlogN).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published.