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 Sam K., 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

More Math practice problems

See all Math problems →