Question

Formatted question description: https://leetcode.ca/all/326.html

 326	Power of Three

 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?

Algorithm

The most straightforward way is to keep dividing by 3 to see if the final iterative quotient is 1. Pay attention to the case where the input is negative and 0.

If no loop, there is a tricky method. Since the input is an int, the range of positive numbers is 0 - 2^31, and the largest power of 3 allowed in this range is 3^19=1162261467, so we only need to see if this number is divisible by n.

Code

Java

public class Power_of_Three {

    public class Solution_math {
        public boolean isPowerOfThree(int n) {
            return (n > 0 && 1162261467 % n == 0);
        }
    }

    public class Solution {
        public boolean isPowerOfThree(int n) {
            if (n < 1) {
                return false;
            }

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

            return n == 1;
        }
    }
}

All Problems

All Solutions