Power of Three

EASY

Description

Given an integer n, return true if it is a power of three. Otherwise, return false.

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

Example 1:

Input: n = 27
Output: true
Explanation: 27 = 3³

Example 2:

Input: n = 0
Output: false
Explanation: There is no x where 3^x = 0.

Example 3:

Input: n = -1
Output: false
Explanation: There is no x where 3^x = (-1).

Constraints:

-2³¹ <= n <= 2³¹ - 1

Follow up: Could you solve it without loops/recursion?

Approaches

Checkout 4 different approaches to solve Power of Three. Click on different approaches to view the approach and algorithm in detail.

Recursive Division

This approach uses recursion to repeatedly check if the number can be divided by 3. The logic is broken down into base cases: a number is a power of three if, after being divided by 3 some number of times, it becomes 1. If at any point it's not divisible by 3 (and is not 1), it's not a power of three.

Algorithm

If n <= 0, it cannot be a power of three, so return false.
If n == 1, it is 3^0, which is a power of three, so return true.
If n is not divisible by 3 (n % 3 != 0), it cannot be a power of three (unless it's 1, which is already handled), so return false.
If none of the above, the number is a positive multiple of 3. Make a recursive call with n / 3 and return its result.

The function isPowerOfThree is defined recursively. It first handles the base cases. Any number less than or equal to 0 cannot be a power of three. The number 1 is the base case for a successful path (3^0 = 1). If the current number n is not divisible by 3, it breaks the chain of powers of three, so we return false. Otherwise, the function calls itself with the argument n / 3, continuing the process until a base case is met.

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

Complexity Analysis

Time Complexity: O(log n) The number of recursive calls is proportional to the logarithm of `n` to the base 3. In each call, we perform constant time operations.Space Complexity: O(log n) Each recursive call adds a new frame to the call stack. The depth of the recursion is the number of times `n` can be divided by 3, which is `log_3(n)`.

Pros and Cons

Pros:

The code can be seen as an elegant and direct translation of the mathematical definition.
It avoids explicit loop constructs.

Cons:

Less space-efficient than the iterative approach due to the recursion call stack.
Can lead to a StackOverflowError for inputs larger than the standard integer types, although this is not an issue with the given constraints.

Code Solutions

Checking out 4 solutions in different languages for Power of Three. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Power of Three

Patterns:

MathRecursion

Companies:

Goldman Sachs |