Skip to main content

326. Power of Three

easy

Decide whether an integer is a power of 3. A throwaway recursion warm-up that exposes a nice math trick at the end — divide the largest 32-bit power of 3 by n and check the remainder.

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

Recursive: if n == 1 return true; if n < 1 or n % 3 != 0 return false; return isPowerOfThree(n / 3).

Hint 2

Iterative: while n > 1 and n % 3 == 0, divide n by 3; return n == 1.

Hint 3

Math trick: 1162261467 is 3^19, the largest power of 3 that fits in a 32-bit int. Return n > 0 and 1162261467 % n == 0.

Hint 4

The math trick runs in O(1) and is the production-grade solution.

Solution approach

Reveal approach

Three approaches. Recursive: isPowerOfThree(n): if n == 1 return true; if n <= 0 or n % 3 != 0 return false; return isPowerOfThree(n / 3). O(log_3 n) time and stack. Iterative: while n > 1 and n % 3 == 0: n /= 3. Return n == 1. Same complexity, no recursion overhead. Constant-time math: the largest 32-bit power of 3 is 3^19 = 1162261467. Any positive power of 3 divides it. So return n > 0 and 1162261467 % n == 0. O(1) — best for production. Mention all three in interviews; default to iterative.

Complexity

Time
O(1) with math trick, O(log n) otherwise
Space
O(1)

Related patterns

  • recursion
  • math
  • iteration

Related problems

Asked at

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

  • Amazon
  • Goldman Sachs

More Recursion practice problems

See all Recursion problems →