326. Power of Three

Difficulty: Easy

Topics: Math, Recursion

Given an integer n, return true if it is a power of three. Otherwise, return false.

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

Example 1:

• Input: n = 27
• Output: true
• Explanation: 27 = 3^3<যsup>

Example 2:

• Input: n = 0
• Output: false
• Explanation: There is no x where 3^x = 0.

Example 3:

• Input: n = -1
• Output: false
• Explanation: There is no x where 3^x = (-1).

Constraints:

• -231 <= n <= 231 - 1

Follow up: Could you solve it without loops/recursion?

Solution:

We need to determine if a given integer n is a power of three. An integer n is a power of three if there exists an integer x such that n == 3x.

Approach

The approach leverages mathematical properties of powers of three within the constraints of 32-bit signed integers. The key insight is that the largest power of three that fits within a 32-bit signed integer is 3¹⁹ = 1162261467. For any positive integer n to be a power of three, it must be a divisor of 3¹⁹. This is because the divisors of 3¹⁹ are exclusively 3^k for k = 0 to 19, which covers all possible powers of three within the 32-bit signed integer range.

1. Check for Non-Positive Values: If n is less than or equal to zero, it cannot be a power of three, so we immediately return false.
2. Divisibility Check: For positive n, we check if 1162261467 (i.e., 3¹⁹) is divisible by n without any remainder. If it is, then n is a power of three; otherwise, it is not.

This approach efficiently checks the power of three condition without using loops or recursion, leveraging mathematical properties for optimal performance.

Let's implement this solution in PHP: 326. Power of Three

<?php
/**
 * @param Integer $n
 * @return Boolean
 */
function isPowerOfThree($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
var_dump(isPowerOfThree(27));   // true
var_dump(isPowerOfThree(0));    // false
var_dump(isPowerOfThree(-1));   // false
var_dump(isPowerOfThree(9));    // true
var_dump(isPowerOfThree(45));   // false
?>

Explanation:

1. Initial Check: The function first checks if n is non-positive (i.e., n <= 0). Since powers of three are always positive, any non-positive n is immediately disqualified, returning false.
2. Divisibility by Largest Power: For positive n, the function checks if the largest 32-bit power of three (1162261467) is divisible by n. If 1162261467 % n == 0, it confirms n is a power of three (specifically, 3^k for some k between 0 and 19), returning true. Otherwise, it returns false.

This method efficiently leverages mathematical properties to avoid loops or recursion, providing an optimal solution with constant time complexity O(1).

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub