Power of Three - Solution & Explanation

Problem Overview: Given an integer n, determine whether it can be written as 3^k for some integer k ≥ 0. In other words, repeatedly multiplying 3 by itself should eventually produce n. If no such exponent exists, the number is not a power of three.

This problem sits in the math category and often appears as a quick test of number properties and integer manipulation. The goal is not brute-force exponent generation but recognizing patterns in powers of three.

Approach 1: Iterative Division (Time: O(log₃ n), Space: O(1))

The simplest way to verify a power of three is repeated division. If n is divisible by 3, divide it by 3 and continue the process. A valid power of three will eventually reduce to exactly 1. If at any step n % 3 != 0, the number contains another prime factor and cannot be expressed as 3^k.

This works because powers of three are composed solely of the factor 3. Every division removes one exponent. The loop runs at most log₃ n times since each step shrinks the value by a factor of three. Memory usage stays constant because only the input variable is modified.

This approach is reliable, easy to implement in any language, and avoids floating‑point precision problems. A recursive version follows the same logic and fits naturally within recursion patterns, but the iterative loop is more efficient in practice.

Approach 2: Mathematical Check Using Logarithms (Time: O(1), Space: O(1))

A number n is a power of three if there exists an integer k such that n = 3^k. Taking logarithms gives k = log(n) / log(3). If the computed value of k is an integer, then n must be a power of three.

The implementation computes k = log10(n) / log10(3) (or using natural logs) and checks whether k is very close to an integer using rounding. This converts the repeated division process into a constant-time mathematical check.

The tradeoff is floating‑point precision. For large values of n, rounding errors can cause near-integer values like 4.999999. Because of this, production code usually compares the difference against a small epsilon or prefers integer division instead.

Recommended for interviews: The iterative division approach is the expected solution. It clearly shows understanding of number factorization and runs in O(log n) time with O(1) space. The logarithm method demonstrates mathematical insight but may introduce precision issues, so interviewers generally favor the division approach for clarity and reliability.