Skip to main content

326. Power of Three

easy

Decide whether an integer is a power of three, ideally without a loop. The trick: 3^19 = 1162261467 is the largest power of three that fits in 32 bits — so n is a power of three iff 1162261467 % n == 0.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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

Constraints

  • -2^31 <= n <= 2^31 - 1

Examples

Example 1

Input
n = 27
Output
true

Explanation: 27 = 3^3.

Example 2

Input
n = 0
Output
false

Explanation: There is no x where 3^x = 0.

Example 3

Input
n = -1
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Loop approach: while n divisible by 3, divide. Return n == 1. O(log3 n) time.

Hint 2

Logarithm approach: check if log(n) / log(3) is an integer. Floating-point precision can lie — be careful.

Hint 3

Constant-time trick: 3^19 = 1162261467 is the largest power of 3 fitting in a signed 32-bit int. Any power of 3 within the int range divides 3^19.

Hint 4

So: return n > 0 && 1162261467 % n == 0.

Solution approach

Reveal approach

Three valid approaches: (1) loop — while n is positive and divisible by 3, divide; return n == 1 at the end. O(log3 n) time. (2) Math identity — return n > 0 && 1162261467 % n == 0 where 1162261467 = 3^19 is the maximum power of 3 in 32-bit range. O(1) time. Only works because 3 is prime, so every divisor of 3^19 must itself be a power of 3. (3) Set lookup — precompute the 20 powers of 3 that fit in int32 and check membership; equally fast. The 3^19 trick is the interview-favorite — concise and demonstrates number-theory awareness.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Power of Three and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →