Power of Three

Power of Three

What is this problem about?

The Power of Three problem asks whether a given integer n is a power of 3 (3^0=1, 3^1=3, 3^2=9, ...). This easy coding problem tests mathematical reasoning through multiple approaches: iteration/recursion, mathematical formula, and an elegant divisibility trick. The math and recursion interview pattern is demonstrated.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it has two clean approaches with very different elegance levels. The loop approach is trivial; the mathematical trick (largest power of 3 in the int range divides n) is impressive. The difference between these approaches signals the candidate's mathematical depth.

Algorithmic pattern used

Multiple approaches:

1. Loop: while n > 1: if n%3 != 0, return false; n //= 3. Return n==1.
2. Math trick: The largest power of 3 fitting in a 32-bit int is 3^19 = 1162261467. Return n > 0 && 1162261467 % n == 0.
3. Log: Return n > 0 && round(log10(n)/log10(3)) == log10(n)/log10(3) (floating-point precision issues).

Example explanation

n=27. Loop: 27/3=9/3=3/3=1. Return true (3^3=27). n=45. 45/3=15/3=5. 5%3≠0. Return false. Math trick: 1162261467 % 27 = 0 → true. 1162261467 % 45 ≠ 0 → false.

Common mistakes candidates make

• Using logarithm with floating-point precision (log3(n) may not be exactly an integer due to float errors).
• Not handling n ≤ 0 (return false for non-positive).
• Off-by-one: 3^0=1, which is valid.
• Using the loop approach without handling n=1 correctly.

Interview preparation tip

Power of Three showcases mathematical insight vs brute force. Always know both: the loop approach (clear, correct) and the largest-power divisibility trick (elegant, O(1)). The trick works only for prime bases (3 is prime, so only exact powers of 3 divide 3^19). Practice Power of Two, Three, and Four together — each has a different O(1) trick. Knowing these demonstrates mathematical sophistication.