Teaching Kids Programming – Algorithms to Check Integer Power of Three

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Recursion Algorithm to Check Power of Three

If n is non-positive, it is not a power of Three. If it is one, it is 3^0. Otherwise, it has to be dividisble by three and we can recursively check n//3.

1
2
3
4
5
6
7

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

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

Time complexity is . Since this may be tail-optimised by compiler, the space complexity is O(1).

Iterative Algorithm to Check Power of Three

The above Recursion can be turned into the iterative approach where we repeatedly divide the number by three if we can until it reaches the 1 (true) or not (false).

1
2
3
4
5
6
7

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

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

Time complexity is . Space complexity is O(1).

Alternatively, we can start from 1 and multiply it 3 until it is larger or equal to n:

1
2
3
4
5
6
7
8

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        i = 1
        while i < n:
            i *= 3
        return i == n

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        i = 1
        while i < n:
            i *= 3
        return i == n

Math Algorithm to Check Power of Three

Since , we know , and further:

We can also replace log function with different bases such as log2, log10, ln ..

1
2
3
4
5
6

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        x = int(log2(n)/log2(3))
        return 3**x==n

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        x = int(log2(n)/log2(3))
        return 3**x==n

The idea is to compute the integer part of x, then reverse check if 3**x == n. Computing log function usually takes O(logN) time (or less if compute has hardware acceleration or lookup tables), and the power function takes O(logN) time as well. Thus the complexity is O(LogN).

This approach may also suffer from floating number precision errors. for example, if we check if x is a integer, we can check if its ceiling and flooring is the same integer. However, this may fail at some test cases such as 243.

1
2
3
4
5
6

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        x = int(log2(n)/log2(3))
        return int(x) == ceil(x)

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        x = int(log2(n)/log2(3))
        return int(x) == ceil(x)

Binary Search Algorithm to Check Power of Three

The last algorithm is the Binary Search Algorithm where we binary search the x.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        left, right = 0, n
        while left <= right:
            mid = (left + right) // 2
            cur = 3 ** mid
            if cur == n:
                return True
            if cur > n:
                right = mid - 1
            else:
                left = mid + 1
        return False

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        left, right = 0, n
        while left <= right:
            mid = (left + right) // 2
            cur = 3 ** mid
            if cur == n:
                return True
            if cur > n:
                right = mid - 1
            else:
                left = mid + 1
        return False

The Binary Search Algorithm is O(logN), however, to compute the Power of Three (O(logN)). The overall complexity is O((logN)^2).

See also: C/C++ Coding Exercise – Power of Three (Leetcode)

–EOF (The Ultimate Computing & Technology Blog) —