Domain 1EasyCORE

Power of Three

The problem asks us to determine whether a given integer `n` is a power of three. In other words, we need to check if there exists an integer `x` such that `n == 3^x`. The input is a single integer `n`, and the output should be a boolean value: `true` if `n` is a power of three, and `false` otherwise.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

326. Power of Three

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 42.1%


Problem Breakdown

The problem asks us to determine whether a given integer n is a power of three. In other words, we need to check if there exists an integer x such that n == 3^x. The input is a single integer n, and the output should be a boolean value: true if n is a power of three, and false otherwise.

Inputs:

  • An integer n.

Outputs:

  • A boolean value (true or false).

Implicit Constraints/Edge Cases:

  • If n is less than 1, it cannot be a power of three (since powers of three are positive).
  • The function should handle the full range of 32-bit signed integers.
  • Consider edge cases like n = 0, n = 1, and very large values.

Intuition

A brute-force approach would involve repeatedly dividing n by 3 until it is no longer divisible, checking if the final result is 1. However, this approach has a time complexity of O(log₃(n)), which is acceptable but not optimal.

The key insight to improve upon this is to leverage mathematical properties. Specifically, we can use the fact that the largest power of three within the range of a 32-bit signed integer is 3^19 = 1162261467. If n is a power of three, it must divide this maximum power of three without leaving a remainder.

Approach

We will use the following approach:

  1. Check if n is less than or equal to 0. If so, return false.
  2. Use the modulo operation to check if 1162261467 % n == 0. If true, then n is a power of three; otherwise, it is not.

This approach leverages the largest power of three within the integer range and avoids loops or recursion.

Complexity Analysis

  • Time Complexity: O(1) - The modulo operation is a constant-time operation.
  • Space Complexity: O(1) - We are using only a fixed amount of extra space.

Solution

def isPowerOfThree(n: int) -> bool:
    # Edge case: n must be positive to be a power of three
    if n <= 0:
        return False
    
    # Check if the largest power of three within 32-bit signed integer range is divisible by n
    return 1162261467 % n == 0

Edge Cases Handled

  • n = 0: The function returns false because 0 is not a power of three.
  • n = 1: The function returns true because 3⁰ = 1.
  • n < 0: The function returns false because negative numbers cannot be powers of three.
  • n > 1162261467: The function returns false because any number greater than the largest power of three within the integer range cannot be a power of three.