326. Power of Three

[mah-shamim]

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?

[mah-shamim]

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) {
    if ($n <= 0) {
        return false;
    }
    $max_power_three = 1162261467;
    return ($max_power_three % $n == 0);
}

// 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).

[topugit]

Thanks for solving the problem of "Power of Three"

[mah-shamim]

Thanks