Skip to main content

Power of Three

Given an integer n, return whether or not it is a power of three.

Note: An integer is a power of three if there exists an integer x such that n = 3^x.

Example(s)​

Example 1:

Input: n = 9
Output: true
Explanation: 9 = 3², so it is a power of three.

Example 2:

Input: n = 50
Output: false
Explanation: 50 is not a power of three.

Example 3:

Input: n = 1
Output: true
Explanation: 1 = 3⁰, so it is a power of three.

Example 4:

Input: n = 27
Output: true
Explanation: 27 = 3³, so it is a power of three.

Example 5:

Input: n = 0
Output: false
Explanation: 0 is not a power of three (3^x > 0 for all x).

Solution​

There are several approaches to solve this problem:

  1. Loop approach: Keep dividing by 3 until we get 1 or a non-divisible number
  2. Recursion approach: Recursively divide by 3
  3. Math approach: Use logarithms (with floating-point precision considerations)
  4. Integer limits approach: Use the maximum power of 3 that fits in an integer

JavaScript Solution - Loop Approach

/**
* Check if n is a power of three using loop
* @param {number} n - Integer to check
* @return {boolean} - True if n is a power of three
*/
function isPowerOfThree(n) {
// Edge cases
if (n <= 0) return false;
if (n === 1) return true;

// Keep dividing by 3
while (n > 1) {
  // If not divisible by 3, it's not a power of three
  if (n % 3 !== 0) {
    return false;
  }
  n = n / 3;
}

return n === 1;
}

// Test cases
console.log('Example 1:', isPowerOfThree(9)); // true
console.log('Example 2:', isPowerOfThree(50)); // false
console.log('Example 3:', isPowerOfThree(1)); // true
console.log('Example 4:', isPowerOfThree(27)); // true
console.log('Example 5:', isPowerOfThree(0)); // false
console.log('Test 6:', isPowerOfThree(81)); // true
console.log('Test 7:', isPowerOfThree(45)); // false
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solutions​

Recursive Approach​

/**
 * Recursive approach
 */
function isPowerOfThreeRecursive(n) {
  // Base cases
  if (n <= 0) return false;
  if (n === 1) return true;
  
  // If not divisible by 3, it's not a power of three
  if (n % 3 !== 0) return false;
  
  // Recursively check n/3
  return isPowerOfThreeRecursive(n / 3);
}

Math Approach (Logarithms)​

/**
 * Math approach using logarithms
 * Note: May have floating-point precision issues
 */
function isPowerOfThreeMath(n) {
  if (n <= 0) return false;
  
  // log₃(n) = log(n) / log(3)
  const log3 = Math.log(n) / Math.log(3);
  
  // Check if log3 is close to an integer
  // Use epsilon to handle floating-point errors
  return Math.abs(log3 - Math.round(log3)) < 1e-10;
}

Integer Limits Approach (Optimal for LeetCode constraints)​

/**
 * Optimal approach using integer limits
 * For 32-bit integers, max power of 3 is 3^19 = 1162261467
 */
function isPowerOfThreeOptimal(n) {
  if (n <= 0) return false;
  
  // Maximum power of 3 that fits in 32-bit signed integer
  const maxPowerOfThree = 1162261467; // 3^19
  
  // If n is a power of 3, it must divide maxPowerOfThree
  return maxPowerOfThree % n === 0;
}

Complexity​

  • Time Complexity: O(log₃(n)) - For loop/recursive approaches, we divide by 3 each time. For the optimal approach, it's O(1).
  • Space Complexity: O(1) - For loop approach. O(log₃(n)) for recursive approach (recursion stack). O(1) for optimal approach.

Approach​

  1. Edge cases: Handle n ≤ 0 (return false) and n = 1 (return true)
  2. Divide by 3: While n > 1, check if n is divisible by 3
  3. Early exit: If n is not divisible by 3, return false
  4. Continue: Divide n by 3 and repeat
  5. Final check: If we reach n = 1, return true

Optimal Approach (For fixed integer size)​

  1. Find maximum: Calculate the maximum power of 3 that fits in the integer type
  2. Divisibility check: If n is a power of 3, it must divide the maximum power of 3
  3. Edge cases: Handle n ≤ 0

Key Insights​

  • Division by 3: Powers of 3 can be reduced to 1 by repeatedly dividing by 3
  • Divisibility: At each step, the number must be divisible by 3
  • Base case: 1 is a power of 3 (3⁰ = 1)
  • Integer limits: For fixed-size integers, we can use the maximum power of 3
  • Logarithm approach: Works but has floating-point precision issues

Step-by-Step Example​

Let's trace through Example 1: n = 9

Initial: n = 9

Step 1: n > 1, check n % 3
  n % 3 = 9 % 3 = 0 ✓ (divisible)
  n = 9 / 3 = 3

Step 2: n > 1, check n % 3
  n % 3 = 3 % 3 = 0 ✓ (divisible)
  n = 3 / 3 = 1

Step 3: n === 1
  Return true

Result: true (9 = 3²)

Let's trace through Example 2: n = 50

Initial: n = 50

Step 1: n > 1, check n % 3
  n % 3 = 50 % 3 = 2 ✗ (not divisible)
  Return false

Result: false (50 is not a power of 3)

Edge Cases​

  • n = 0: Not a power of 3 (return false)
  • n = 1: Is a power of 3 (3⁰ = 1, return true)
  • n < 0: Not a power of 3 (return false)
  • n = 3: Is a power of 3 (3¹ = 3, return true)
  • Very large n: Loop approach handles it, optimal approach is O(1)

Mathematical Properties​

  • 3⁰ = 1: Base case
  • 3¹ = 3: First power
  • 3² = 9: Second power
  • 3³ = 27: Third power
  • Pattern: Each power is 3 times the previous power

Comparison of Approaches​

ApproachTimeSpaceNotes
LoopO(log₃(n))O(1)Simple, easy to understand
RecursiveO(log₃(n))O(log₃(n))Clean but uses stack space
Math (log)O(1)O(1)Fast but precision issues
OptimalO(1)O(1)Fastest, but only works for fixed integer size
  • Power of Two: Similar problem for base 2
  • Power of Four: Similar problem for base 4
  • Count Primes: Different but related number theory problem
  • Factorial Trailing Zeroes: Another number theory problem

Takeaways​

  • Loop approach is simple and works for any integer size
  • Recursive approach is elegant but uses more space
  • Optimal approach is fastest for fixed-size integers
  • Edge cases are important (0, 1, negative numbers)
  • Divisibility check is the key insight