Skip to main content

326. Power of Three

easyAsked at Goldman Sachs

Return true if n is a power of three. Goldman Sachs uses this as a brainteaser: they want to see whether you can produce a loop-free, branch-free, O(1) solution that exploits a clever number-theory fact.

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

Source citations

Public interview reports confirming this problem appears in Goldman Sachs loops.

  • Glassdoor (2026-Q1)— Goldman Sachs SWE candidates report Power of Three as a brainteaser with the explicit follow-up 'can you do it without loops or recursion?'.
  • LeetCode Discuss (2025-10)— Power of Three is in the top-30 of LeetCode's Goldman Sachs company tag.

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. Follow up: could you solve it without loops or recursion?

Constraints

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

Examples

Example 1

Input
n = 27
Output
true

Example 2

Input
n = 0
Output
false

Example 3

Input
n = -1
Output
false

Approaches

1. Iterative division by 3

Keep dividing n by 3 while it's divisible. If you end at 1, it's a power of 3.

Time
O(log n)
Space
O(1)
function isPowerOfThreeIter(n) {
  if (n < 1) return false;
  while (n % 3 === 0) n = n / 3;
  return n === 1;
}

Tradeoff: Clear and correct. Mention it as your first answer, then handle the 'without loops' follow-up.

2. Largest-power-of-3 divisibility trick (optimal)

The largest power of 3 that fits in a signed 32-bit int is 3^19 = 1162261467. If n is a power of 3, then n divides 1162261467 exactly.

Time
O(1)
Space
O(1)
function isPowerOfThree(n) {
  return n > 0 && 1162261467 % n === 0;
}

Tradeoff: Constant time, no loops. Works because 3 is prime, so the only divisors of 3^19 are themselves powers of 3. Goldman loves this answer because it shows you understand the number-theory invariant.

3. Logarithm trick

Compute log_3(n) and check if it's an integer.

Time
O(1)
Space
O(1)
function isPowerOfThreeLog(n) {
  if (n < 1) return false;
  const x = Math.log10(n) / Math.log10(3);
  return Math.abs(x - Math.round(x)) < 1e-10;
}

Tradeoff: O(1) but floating-point — the epsilon is fragile and Goldman will probe whether you understand the precision risk. Mention it but lead with the divisibility trick.

Goldman Sachs-specific tips

Goldman Sachs interviewers are explicitly looking for the divisibility-by-3^19 trick on this question — it's the canonical 'I see why 3 being prime matters' insight. The reasoning chain to articulate: '3 is prime → any power of 3 only has prime factors of 3 → so a power of 3 in 32-bit space must divide the largest power of 3 that fits, namely 3^19'. State that chain on the whiteboard before writing code.

Common mistakes

  • Forgetting the n > 0 guard — 0 and negatives are not powers of 3.
  • Using the float log version without an epsilon, which fails on cases like 243 due to precision.
  • Computing 3^19 at runtime instead of hard-coding the constant — both work but the constant signals you understood why it's the answer.

Follow-up questions

An interviewer at Goldman Sachs may pivot to one of these next:

  • Generalize: power of any prime k. (Same trick — largest k^x that fits, divisibility.)
  • Power of 2. (Bit trick: n > 0 && (n & (n-1)) === 0.)
  • Power of 4 — needs both 'power of 2' AND 'bit set is at an even position'.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Does the divisibility trick work for power-of-2?

No — because 2 is prime, 2^30 = 1073741824 is divisible by every power of 2 up to itself, BUT also by 2, 4, 8, ... which are all powers of 2 already. The trick works for ALL primes k. For non-primes it breaks (4^x is also 2^(2x) and 2^(2x) | 2^30 doesn't imply 4 | x).

Why is 1162261467 the magic number?

Because 3^19 = 1162261467 and 3^20 = 3486784401 > 2^31 - 1 = 2147483647, so 3^19 is the largest power of 3 that fits in a signed 32-bit int.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Power of Three and other Goldman Sachs interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →