Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Power of Three solution and explanation

EasyMathRecursion5 min read51.4% acceptanceUpdated 9 Apr 2026
Asked atGoogleBloombergAmazonMicrosoftMetaGoldman Sachs
Practise Power of Three
3:16
Power of Three | Live Coding with Explanation | Leetcode - 326Algorithms Made Easy · 3:16 · 14K viewsWatch on YouTube
9 more videos on this problem
  1. Power of Three | Live Coding with Explanation | Leetcode - 326Algorithms Made Easy · 3:16 · 14K views
  2. LeetCode - 326. Power of Three | Day 27 April ChallengeAditya Mahajan · 10:11 · 6K views
  3. AirBnB Coding Interview Question - Power Of Three - LeetCode 326AlgoJS · 4:31 · 2K views
  4. 326. Power of Three | Leetcode Daily - PythonLeetcode Daily · 5:27 · 646 views
  5. 326 Power of Three LeetCode Problem in C++ | LeetCode for Beginners | LeetCode SolutionCoding enthusiast · 3:10 · 543 views
  6. LeetCode 326 : Power of Three || EASY || JAVA || Detailed SolutionCodeGPT · 5:08 · 300 views
  7. 💻Solving All LeetCode Problems with PYTHON 🐍 - 326 Power of ThreeAlex Brou · 4:45 · 191 views
  8. Power of Three | LeetCode 326 | Easy Math + Logic ExplainedCode Harmony · 16:56 · 187 views
  9. Crack LeetCode 326. Power of Three Coding Interview Question! 🤯 | Two Mind-Blowing Methods ExplainedvanAmsen · 5:02 · 83 views
  10. LeetCode 326 Power of Three in Python | Easy Coding Tutorial for BeginnersJR: Educational Channel · 1:13 · 77 views

The problem

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.

def isPowerOfThree(n: int) -> bool:
    if n < 1:
        return False
    while n % 3 == 0:
        n //= 3
    return n == 1
public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}
#include <iostream>
using namespace std;

bool isPowerOfThree(int n) {
    if (n < 1) return false;
    while (n % 3 == 0) {
        n /= 3;
    }
    return n == 1;
}
function isPowerOfThree(n) {
    if (n < 1) return false;
    while (n % 3 === 0) {
        n /= 3;
    }
    return n === 1;
}
#include <stdbool.h>

bool isPowerOfThree(int n) {
    if (n < 1) return false;
    while (n % 3 == 0) {
        n /= 3;
    }
    return n == 1;
}
public class Solution {
    public bool IsPowerOfThree(int n) {
        if (n < 1) return false;
        while (n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
}

The Python function checks divisibility by 3 until n becomes 1 or stops being divisible by 3, indicating it's not a power of 3.

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.

import math

def isPowerOfThree(n: int) -> bool:
    if n < 1:
        return False
    log_res = math.log10(n) / math.log10(3)
    return log_res.is_integer()
public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) return false;
        double logRes = Math.log10(n) / Math.log10(3);
        return (logRes - (int)logRes) == 0;
    }
}
#include <cmath>

bool isPowerOfThree(int n) {
    if (n < 1) return false;
    double logRes = log10(n) / log10(3);
    return (logRes - (int)logRes) == 0;
}
function isPowerOfThree(n) {
    if (n < 1) return false;
    let logRes = Math.log10(n) / Math.log10(3);
    return (logRes - Math.floor(logRes)) === 0;
}
#include <stdbool.h>
#include <math.h>

bool isPowerOfThree(int n) {
    if (n < 1) return false;
    double logRes = log10(n) / log10(3);
    return (logRes - (int)logRes) == 0;
}
using System;

public class Solution {
    public bool IsPowerOfThree(int n) {
        if (n < 1) return false;
        double logRes = Math.Log10(n) / Math.Log10(3);
        return (logRes - (int)logRes) == 0;
    }
}

In Python, this function calculates logarithms and uses the is_integer() method to verify if we have an integer result, suggesting n is a power of three.

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

function isPowerOfThree(n: number): boolean {
    while (n > 2) {
        if (n % 3 !== 0) {
            return false;
        }
        n = Math.floor(n / 3);
    }
    return n === 1;
}
func isPowerOfThree(n int) bool {
	for n > 2 {
		if n%3 != 0 {
			return false
		}
		n /= 3
	}
	return n == 1
}
impl Solution {
    pub fn is_power_of_three(mut n: i32) -> bool {
        while n > 2 {
            if n % 3 != 0 {
                return false;
            }
            n /= 3;
        }
        n == 1
    }
}
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).

function isPowerOfThree(n: number): boolean {
    return n > 0 && 1162261467 % n == 0;
}
func isPowerOfThree(n int) bool {
	return n > 0 && 1162261467%n == 0
}
impl Solution {
    pub fn is_power_of_three(mut n: i32) -> bool {
        n > 0 && 1162261467 % n == 0
    }
}
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–

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.

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.

Comments

Next problem · similarPower of TwoEasy
Now write it yourselfClose this page and solve Power of Three in the editor, without looking.
Practise Power of Three