Power of Three

Easymath
Category: Fundamentals
Companies that ask this question:
AmazonGoogle
LeetCode →

Approach

Power of Three

Approach

Repeatedly divide by 3 until not divisible.

Algorithm

  1. Handle n ≤ 0: return false
  2. While n divisible by 3: divide by 3
  3. Return true if n becomes 1

Complexity

  • Time: O(log n) - divisions reduce n
  • Space: O(1) - constant space

Key Insights

  • Power of 3: 1, 3, 9, 27, 81, ...
  • Repeatedly dividing by 3 reduces to 1
  • Alternative: use 3^19 % n == 0 (largest 32-bit power)

Solution

java
1class Solution {
2    public boolean isPowerOfThree(int n) {
3        if (n <= 0) return false;
4        
5        while (n % 3 == 0) {
6            n /= 3;
7        }
8        
9        return n == 1;
10    }
11}
Loading visualizer...