326. Power of Three

Time: O(log n)

Space: O(1)

Intuition

The largest power of 3 that fits in an int is 3^19 = 1,162,261,467. A number n is a power of 3 iff it divides this maximum power exactly.

Algorithm

1Return n > 0 && 1162261467 % n == 0.

Example Walkthrough

Input: n = 9

1.1162261467 % 9 = 0. Return true.

Output: true

Common Pitfalls

•This only works because 3 is prime - the same trick does not apply to composite bases (e.g., 6 is not a power of 2 or 3 but 12 % 6 = 0).

326.cs

// Approach: Repeatedly divide by 3; the number is a power of three
// if and only if the result reduces to exactly 1.
// Time: O(log n) Space: O(1)

public class Solution
{
    public bool IsPowerOfThree(int n)
    {
        if (n == 0)
            return false;

        while (n % 3 == 0)
            n /= 3;

        return n == 1;
    }
}

public class Solution1
{
    public bool IsPowerOfThree(int n)
    {
        // 1162261467 is the maximum integer that is a power of three
        // (it is 3^19, as 3^20 is bigger than int).
        // If 'n' is a power of three, it must divide this number without a remainder.

        // The condition 'n > 0' ensures that 'n' is positive,
        // because negative numbers and zero cannot be powers of three.
        return n > 0 && 1162261467 % n == 0;
    }
}

Was this solution helpful?