Leetcode – Power of Three Solution in Python

Spread the love

In this extensive article, we will delve into a widely-recognized problem on LeetCode named ‘Power of Three’. This problem is essential for understanding mathematical properties and optimization techniques. We will dissect the problem statement, explore various methods to solve it, and evaluate their time and space complexities.

Introduction

Let’s first look at the problem statement:

Given an integer n, write a function to determine if it is a power of three.

Example:

Input: n = 27

Output: True

Explanation: 27 is 3^3, hence it is a power of three.

Understanding the Problem

The problem is quite straightforward: we need to ascertain if the given integer n is a power of three. In other words, we need to check if there exists an integer x such that 3^x = n.

Approach 1: Loop Iteration

The most intuitive approach is to keep dividing the number by three and check if we reach 1.

  1. If n is less than 1, return False.
  2. While n is greater than 1, check if n is divisible by 3. If it is, divide n by 3; otherwise, return False.
  3. If the loop ends, return True.
def isPowerOfThree(n):
    if n < 1:
        return False
        
    while n > 1:
        if n % 3 != 0:
            return False
        n /= 3
        
    return True

Time Complexity:

O(log₃n) – In the worst case, we keep dividing the number by 3 until we reach 1.

Space Complexity:

O(1) – We are not using any additional data structures.

Approach 2: Logarithm

We can also solve this problem using logarithms. If n is a power of three, then log₃(n) must be an integer. We can calculate the base 3 logarithm by using the change of base formula: log₃(n) = log₁₀(n) / log₁₀(3).

  1. If n is less than 1, return False.
  2. Calculate log₃(n) using the change of base formula.
  3. Check if log₃(n) is an integer. If it is, return True; otherwise, return False.
import math

def isPowerOfThree(n):
    if n < 1:
        return False
    
    log3_n = math.log10(n) / math.log10(3)
    return math.isclose(log3_n, round(log3_n))

Time Complexity:

O(1) – We perform a constant number of operations.

Space Complexity:

O(1) – No additional space is required.

Approach 3: Mathematical Property

There is a mathematical trick we can use. The maximum value of an integer in most systems is 2¹⁶⁻¹. The largest number that is a power of three and fits into an integer is 3¹⁹ = 1162261467. We can observe that 1162261467 is divisible by all powers of three less than or equal to it. Therefore, we can simply check if 1162261467 is divisible by n.

  1. If n is less than 1, return False.
  2. Return True if 1162261467 is divisible by n; otherwise, return False.
def isPowerOfThree(n):
    return n > 0 and 1162261467 % n == 0

Time Complexity:

O(1) – We perform a constant number of operations.

Space Complexity:

O(1) – No additional space is used.

Conclusion:

The Power of Three problem on LeetCode is an exemplary case of how different approaches can be used to solve a relatively simple mathematical problem. Each approach has its own merits and demerits. The loop iteration is a brute-force method, the logarithm approach uses mathematical properties, and the third approach uses a clever mathematical trick.

Leave a Reply