Power Of Three - Leetcode Solution

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: -231 <= n <= 231 - 1

Solution:

Approach 1: Iterative Division One straightforward approach to the given problem could be to repeatedly divide the given number n by three, until we reach one. If we encounter any remainder other than 0 during the division, we can instantly return false as the number is not a power of three. Once we reach a stage where the given number becomes one, we can return true as we would have validated that it is a power of three.

Let's see the implementation of this approach.

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

In the above code, we have a loop that runs until the given number becomes one. During each iteration, we check if the current number is divisible by 3. If it is not, we instantly return false. If it is, we proceed to divide the number by 3. Finally, if we reach a stage where the given number becomes one, we return true.

The time complexity of this approach is O(log n), as we are dividing the input number n by three in each iteration.

Approach 2: Base Conversion Another approach to the given problem involves converting the given number to a base 3 string and checking if it has only one leading digit of "1" followed by zero or more "0's".

Let's see the implementation of this approach.

class Solution: def isPowerOfThree(self, n: int) -> bool: if n == 0: return False base3 = base2 = '' while n: base3 = str(n % 3) + base3 n //= 3 return base3 == '1' + '0' * (len(base3) - 1)

In the above code, we first handle the edge case where the given number is 0. Then we convert the given number to its base 3 representation by repeatedly dividing it by three, and appending the remainder to a string. Note that the base 3 representation of a number can be found by successively dividing the number by 3 and recording the remainders in reverse order.

Once we have the base 3 representation of the given number, we check if it has only one leading digit of 1 followed by zero or more "0's". If it has any other digit or any non-zero digit other than the leading digit, we instantly return false. Otherwise, we return true.

The time complexity of this approach is O(log n), as we are repeatedly dividing the input number n by three in each iteration.

Approach 3: Integer Logarithm One more approach to the given problem is to use the integer logarithm base 3 of the given number. If the integer logarithm is an integer, we can conclude that the given number is a power of three.

Let's see the implementation of this approach.

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

In the above code, we first handle the edge case where the given number is negative or 0. Then we compute the integer logarithm base 3 of the given number using the formula log3(n) = log10(n) / log10(3). Finally, we check if the integer part of the result is equal to the result itself. If it is, we return true.

The time complexity of this approach is O(1), as we are using the logarithmic function to compute the integer logarithm. However, computing the logarithm can be an expensive operation, so the actual running time of this approach might not be efficient.

1