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

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

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →