Power of Three

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

Power of Three Solve

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 3^x, right? (where x is an integer)

That means, if we divide n by 3, we'll end up getting 3^x-1, and then if we divide again, then 3^x-2, and so on and finally we'll reach 3⁰ 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.

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

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

    return (n == 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.

bool isPowerOfThree(int n) {
    if(!n)
        return false;
    if(n == 1)
        return true;
    
    return (n%3) ? false : isPowerOfThree(n/3);
}

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.