LeetCode 326: Power of Three

Problem Restatement

We are given an integer n.

Return true if n is a power of three. Otherwise, return false.

A number is a power of three when it can be written as:

n = 3^x

where x is an integer.

Examples:

27 = 3^3
9  = 3^2
3  = 3^1
1  = 3^0

So 27, 9, 3, and 1 are powers of three.

Numbers like 0, 2, 6, 12, and 45 are not powers of three.

Input and Output

Function shape:

def isPowerOfThree(n: int) -> bool:
    ...

Examples

Example 1:

Input: n = 27
Output: true

Explanation:

27 = 3 * 3 * 3 = 3^3

So 27 is a power of three.

Example 2:

Input: n = 0
Output: false

No integer power of three gives 0.

Example 3:

Input: n = -1
Output: false

Powers of three are positive, so -1 cannot be a power of three.

First Thought: Brute Force

One direct way is to keep generating powers of three:

1, 3, 9, 27, 81, ...

Stop when the generated value becomes greater than or equal to n.

If we reach n, return true.

Otherwise, return false.

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False

        power = 1

        while power < n:
            power *= 3

        return power == n

This works, but there is another equally simple way that follows the definition more directly.

Key Insight

If n is a power of three, then it can be divided by 3 repeatedly until it becomes 1.

For example:

27 -> 9 -> 3 -> 1

Every step divides cleanly by 3.

But consider 45:

45 -> 15 -> 5

Now 5 cannot be divided by 3 cleanly.

So 45 is not a power of three.

The key rule is:

A positive number is a power of three if repeated division by 3 eventually reaches 1 with no remainder.

Algorithm

First handle non-positive numbers.

If n <= 0, return false.

Then repeatedly divide n by 3 while it is divisible by 3.

At the end, check whether the result is exactly 1.

Steps:

1. If n <= 0, return false.
2. While n % 3 == 0, divide n by 3.
3. Return whether n == 1.

Walkthrough

Take:

n = 27

Since 27 is divisible by 3, divide:

27 / 3 = 9

Since 9 is divisible by 3, divide:

9 / 3 = 3

Since 3 is divisible by 3, divide:

3 / 3 = 1

Now n is 1.

So the answer is true.

Now take:

n = 45

Divide by 3:

45 / 3 = 15

Divide by 3 again:

15 / 3 = 5

Now 5 % 3 != 0.

We stop. The final value is 5, not 1.

So the answer is false.

Correctness

The algorithm only divides by 3 when the current value is exactly divisible by 3.

If the original number is 3^x, then each division removes one factor of 3:

3^x -> 3^(x - 1) -> 3^(x - 2) -> ... -> 3^0

Since 3^0 = 1, every valid power of three eventually becomes 1.

For a number that has any prime factor other than 3, repeated division by 3 cannot remove that factor. The process will stop at a value greater than 1.

For zero or negative numbers, the answer is immediately false, since powers of three are positive.

Therefore, the algorithm returns true exactly when n is a power of three.

Complexity

More precisely, the number of loop iterations is proportional to log_3(n).

Implementation

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False

        while n % 3 == 0:
            n //= 3

        return n == 1

Code Explanation

We first reject zero and negative numbers:

if n <= 0:
    return False

Then we divide by 3 as long as division is exact:

while n % 3 == 0:
    n //= 3

For a true power of three, this loop eventually reaches 1.

Finally:

return n == 1

This returns true for values like 1, 3, 9, and 27.

It returns false for values like 0, -1, 2, 6, 12, and 45.

Testing

def run_tests():
    s = Solution()

    assert s.isPowerOfThree(27) == True
    assert s.isPowerOfThree(9) == True
    assert s.isPowerOfThree(3) == True
    assert s.isPowerOfThree(1) == True

    assert s.isPowerOfThree(0) == False
    assert s.isPowerOfThree(-1) == False
    assert s.isPowerOfThree(2) == False
    assert s.isPowerOfThree(6) == False
    assert s.isPowerOfThree(12) == False
    assert s.isPowerOfThree(45) == False

    print("all tests passed")

run_tests()

Test meaning: