Scale Engineer

Power of Three

Easy
#0313Time: 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: 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)`.1 company
Patterns
MathRecursion
Companies
Goldman Sachs

Prompt

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 == 3x.

 

Example 1:

Input: n = 27
Output: true
Explanation: 27 = 33

Example 2:

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

Example 3:

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

 

Constraints:

  • -231 <= n <= 231 - 1

 

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

Approaches

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

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)`.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem