Skip to main content
Talentd

Power of Three - Solution & Explanation

EasyMathRecursion14 min readAsked at: Amazon, Microsoft, Goldman Sachs +3
Practice this problem

Problem Statement

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?

Approach Overview

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.

Approach 1: Iterative Division

This approach leverages the fact that if a number n is a power of three, it should be divisible by 3 repeatedly until it becomes 1. If at any step, n is not divisible by 3 and it's greater than 1, it cannot be a power of three.

The function checks divisibility by 3 in a loop, dividing n repeatedly by 3 until it is either 1 (return true) or it isn't divisible by 3 anymore (return false).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Mathematical Check Using Logarithms

This approach uses logarithms to determine if a number is a power of three. By taking the logarithm of the number and comparing it to the logarithm base 3, we can check if they form an integer ratio.

This solution calculates the base 10 logarithm of n and divides it by the base 10 logarithm of 3. If the resulting value is an integer, then n is a power of three.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Trial Division

If n \gt 2, we can continuously divide n by 3. If it's not divisible, it means n is not a power of 3, otherwise we continue dividing by 3 until n is less than or equal to 2. If n equals 1, it means n is a power of 3, otherwise it's not a power of 3.

Time complexity O(log_3n), space complexity O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Mathematics

If n is a power of 3, then the maximum value of n is 3^{19} = 1162261467. Therefore, we only need to check if n is a divisor of 3^{19}.

Time complexity O(1), space complexity O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Division

Time Complexity: O(log n)
Space Complexity: O(1)

Mathematical Check Using Logarithms

Time Complexity: O(1)
Space Complexity: O(1)

Trial Division—
Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative DivisionO(log₃ n)O(1)Best general solution. Reliable integer arithmetic with no floating‑point issues.
Mathematical Logarithm CheckO(1)O(1)Useful for quick mathematical validation when floating‑point precision is acceptable.

Video Solution

Power of Three | Live Coding with Explanation | Leetcode - 326 • Algorithms Made Easy • 14,889 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Power of Three easy or hard?
Power of Three is classified as an Easy problem on most coding platforms. The logic relies on recognizing that powers of three contain only the prime factor 3 and verifying this using repeated division.
Power of Three Python/Java solution
In Python or Java, the typical solution uses a loop: while n % 3 == 0, divide n by 3. After the loop, check whether n equals 1. This approach runs in O(log n) time and works consistently across languages without precision issues.
How to solve Power of Three in O(1)?
A constant‑time approach uses logarithms. Compute k = log(n) / log(3) and check whether k is an integer. If the result is very close to an integer value, n can be represented as 3^k. This method runs in O(1) time but requires careful handling of floating‑point precision.
What is the best approach for Power of Three?
The iterative division approach is the most reliable solution. Repeatedly divide the number by 3 while it is divisible. If the value eventually becomes 1, the number is a power of three. This runs in O(log n) time with constant O(1) space and avoids floating‑point precision issues.
Is Power of Three asked at Google/Amazon/Meta?
Power of Three is a common warm‑up style interview problem used by companies like Google, Amazon, and Meta to test understanding of number properties and basic mathematical reasoning. It often appears in early interview rounds or coding assessments.
What data structure is used in Power of Three?
No specialized data structure is required. The problem is primarily a mathematical check using integer arithmetic. The typical implementation uses a loop and modulo operations to repeatedly divide the number by 3.
What is the time complexity of Power of Three?
The standard iterative solution runs in O(log₃ n) time because the number is divided by 3 in every iteration. Each step reduces the magnitude of n by a factor of three. Space complexity remains O(1) since only a single variable is updated.

Ready to solve this problem?

Practice Power of Three with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if Number is a Sum of Powers of Three

Next

Power of Four