Power of Three

Problem#

Return true iff n is a positive integer power of three.

Examples#

• n=27 → true; n=0 → false; n=9 → true.
• n=45 → false.

Constraints#

• -2^31 <= n <= 2^31 - 1.

Approach#

The largest 32-bit power of 3 is 3^19 = 1162261467. n is a power of 3 iff n > 0 and 1162261467 % n == 0.

Solution#

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

func isPowerOfThree(n int) bool {
    return n > 0 && 1162261467%n == 0
}

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 1162261467 % n == 0

function isPowerOfThree(n) {
    return n > 0 && 1162261467 % n === 0;
}

class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

function isPowerOfThree(n: number): boolean {
    return n > 0 && 1162261467 % n === 0;
}

Editorial#

3 is prime, so every divisor of 3^19 is itself a power of 3. This collapses the test to a single modulo. The alternative while (n % 3 == 0) n /= 3; return n == 1; is also O(log n) and just as clear if you don’t recall the constant.

Complexity#

• Time: O(1).
• Space: O(1).

Concept revision#

Related#

• Power of Two