In the last blog, we solved leetcode problem titled as "Power of two". The problem we are going to solve in this blog and the next one is quite similar.
Leetcode problem number: 326
Problem statement:
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.
Output format:
True or False
Thought process: Like previous problem, any number n can be:
- Odd
- Even
- Zero
Like, "power of 2", One's digit of any number which can be written as power of 3 forms a pattern:
3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
... and this pattern goes on like: 3,9,7,1... BUT
We know that If the units digit (or ones digit) is 1,3, 5, 7, or 9, then the number is called an odd number. The pattern we have has only one number missing "5". So, basically all odd numbers except those with 5 at one's digit can be written as a power of 3 !!
From previous blog we also know that for n = 0, we have to return False and n = 1, we simply have to return True (3^0 = 1) So, from what we know till now:
def isPowerOfThree(self, n: int) -> bool:
if n == 0:
return False
if n == 1:
return True
#Keep on checking for divisibility of n by 3 recursively
return n %3 == 0 and isPowerOfThree(n//3)
The above code is not handling one case, when n is even. Clearly no even number can be written as a power of three because: if the units digit is 0, 2, 4, 6, or 8, then the number is called an even number and all we have is the repeating pattern of 3,9,7,1 at one's digit. So, for any even number n, we simply have to return False. The final piece of code:
def isPowerOfThree(self, n: int) -> bool:
if n == 0 or n%2 ==0:
return False
if n == 1:
return True
# the case when one's digit will be 5 will be handled by n%3 ==0
#in this case n%3==0 will return False
return n %3 == 0 and isPowerOfThree(n//3)
If you have any suggestions, reach out to me at: tanishkaashi567@gmail.com
Follow me on github for more: Github
