# 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 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^{0} 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(Log_{3}N)

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) {
if(!n)
return false;
if(n == 1)
return true;
return (n%3) ? false : isPowerOfThree(n/3);
}
```

## Time & Space Complexity

Time: O(Log_{3}N)

Space: O(Log_{3}N)

_{3}N 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.