Given an integer, write a function to determine whether it is a power of 3. Return true if it is; otherwise, return false.

An integer n is a power of 3 if there exists an integer x such that n == 3x.

Example 1:

Input:n = 27
Output:true

Example 2:

Input:n = 0
Output:false

Example 3:

Input:n = 9
Output:true

Example 4:

Input:n = 45
Output:false

Constraints:

• -231 <= n <= 231 - 1

Follow-up:

• Can you solve this problem without using loops or recursion?

Approach

#

This problem is actually simple, whether or not recursion is used.

Recursion follows the usual idea: keep dividing by 3. If the result is exactly 1, the number is a power of 3; if anything else remains, it is not.

The non-recursive approach is also conventional. Powers have the property that their factors include every smaller (or equal) power of 3. Therefore, we only need to choose the largest possible power of 3, N, within the 32-bit integer range (1162261467), and determine whether the given number is a factor of N. If it is, it must be a power of 3.

Rust Code

#

# struct Solution;
impl Solution {
    pub fn is_power_of_three(n: i32) -> bool {
        if n % 3 == 0 && n != 0 {
            Self::is_power_of_three(n / 3)
        } else {
            n == 1
        }
    }
}

C++ Code

#

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}