Skip to main content

Recursion Basics

Power of Three

Okay, as promised, 1 last problem before diving in to the time & space complexity part.

Power of Three

This problem, also, is a straight forward one. We'll be given an integer n, which can be positive as well as negative as well.

Our target is to check whether the given integer is a power of 3 or not? For e.g. 1, 3, 9, 27, 81 etc. are powers of 3, whereas 6, 10, 15, 30 etc. are not.

Iterative way

Of course there isn't just a single way of doing it, there could be other ways as well, but I'll share the one which comes to my mind naturally.

If a number n is a power of 3, then n can be written as 3x, right? (where x is an integer)

That means, if we divide n by 3, we'll end up getting 3x-1, and then if we divide again, then 3x-2, and so on and finally we'll reach 30 i.e. 1.

So, the crux is that keep dividing the given value n with 3, until is divisible by 3. If the eventual value that you get is equal to 1, then the answer is a bit fat YES, otherwise NO.

Implementation (iterative)
bool isPowerOfThree(int n) {
    if(n == 0)
        return false;

    while(n%3 == 0)
        n /= 3;

    return (n == 1);
Time & Space Complexity

Time: O(Log3N)
Space: O(1)

Recursive Way

The recursive way is neat & pretty. The general idea behind it is that if the given number n is not a multiple of 3, then we can confidently say that it's not a power of 3, but if it is divisible by 3, we're not sure.

In this case, we'll simply make a recursive call to check whether n/3 is a power of 3 or not? if yes, we'll return true, else false.

1 thing left for you to think is the base case(s), do give it a thought before diving into the implementation.

Implementation (recursive)
bool isPowerOfThree(int n) {
        return false;
    if(n == 1)
        return true;
    return (n%3) ? false : isPowerOfThree(n/3);
Time & Space Complexity

Time: O(Log3N)
Space: O(Log3N)

The idea is similar to what was explained in the last article, which is that because n is divided by 3 in each recursive call, it'll take approximately Log3N recursive calls to finally reach the base case.
The exact details, will explain in the next few articles, stay tuned.
I think these problems are enough for the basics. Let's quickly cover the time & space complexity in the coming articles and more to Sorting & Searching.