Power of 3

Problem

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

Example 1:

Input: 27

Output: true

Example 2:

Input: 0

Output: false

Example 3:

Input: 9

Output: true

Example 4:

Input: 45

Output: false

Follow up:

Could you do it without using any loop / recursion?

Solution

The brutal force solution is to divide the number by 3, whenever the number mode 3 is not 0, we stop the loop. The cost is O(N).

The follow up question is kind of brain storm.

Here are two of the solutions:

1. convert the 10 base number to 3 based, then the 3 based number should start with 1, followed by 0s. The time cost will be logN/log3, the cost is also logN/log3.
2. find the largest possible integer that is power of 3, that number divide the number we need to exam, then we can tell. The time cost and space cost is O(1).

public class PowerOfThree {
  public static boolean isPowerOfThree(int i) {
    return Integer.toString(i,3).matches("^10*$");
  }
  public static int max3Power() {
    int n = (int)(Math.log(Integer.MAX_VALUE + 0.0)/Math.log(3 + 0.0));
    return (int) Math.pow(3.0, n);
  }
  public static boolean isPowerOfThree2(int n) {
    //int max3power = max3Power();
    return n > 0 && 1162261467 % n == 0; 
  }
  public static void main(String[] args) {
    System.out.println(isPowerOfThree(81));
    System.out.println(isPowerOfThree(80));
    System.out.println(isPowerOfThree2(81));
    System.out.println(isPowerOfThree2(80));
    System.out.println(max3Power());
  }
}

Time cost O(1), Space cost O(1).