Power of Three

Problem

Given an integer, write a function to determine if it is a power of three.

Follow up: Could you do it without using any loop / recursion?

Solution

Regular Iterative Solution: O(n) time O(1) space

public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) return false;
        while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}

Smart Use of Integer.MAX_VALUE Solution: 3^19
O(1) time and O(1) space

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && Math.pow(3, 19) % n == 0;
    }
}

Analysis

When it comes to power of a specif number, think of the biggest possible number
Use that number to determine if given number is qualified
Remember that Integer.MAX_VALUE = 2^31 - 1