The easiest way to go about this is to think about how exponents work. When you see 3^6, you are multiplying 3 by 3 exactly 6 times.

With that said, we can simply reverse the direction: we can take the result, and continuously divide it by 3. If we eventually get to 1, we know that it's been divisible all along and is thus an exponent of 3.

Complexity of Final Solution

Since we are dividing by 3 for every iteration in the while loop, we find our answer after roughly log3(n) (base 3) iterations for O(logn) time complexity. We do not use any additional data structures, so we use O(1) constant space.