326. Power of Three

Problem Description

The task is to determine if a given integer n is a power of three. In other words, you need to check if there exists an integer x such that when you raise 3 to the power of x (3^x), the result is n. This is a binary decision problem where the output is either true if n is a power of three or false if it is not.

Intuition

The intuition behind the solution is based on number theory. First, notice that if n is less than or equal to zero, it cannot be a power of three. Hence, we first check that n is positive. Next, we observe that if n is a power of three, n must be a divisor of the largest power of three that fits in a signed 32-bit integer, because the powers of three are spread at constant ratios and every power of three is a multiple of smaller powers of three.

The number 1162261467 is used in the provided solution because it is the largest power of three (3^19) that fits in a signed 32-bit integer range. If n is truly a power of three, it must divide this number without leaving a remainder. This is based on the properties of exponents in which any lower power of the base (in this case, three) will be a factor of the higher powers of the base.

The condition 1162261467 % n == 0 is checking for this exact scenario. If n is a power of three, the modulo operation will result in zero meaning n divides 1162261467 exactly, validating that n is a power of three.

Learn more about Recursion and Math patterns.

Solution Approach

The implementation of the solution is straightforward and does not require complex algorithms or data structures. It is a matter of a single comparison and a modulo operation. Here's a step-by-step walkthrough of the code provided:

The condition n > 0 ensures that we disregard any non-positive integers. Numbers less than or equal to zero cannot be a power of three, so this condition quickly handles these cases by returning false.
For positive values of n, the solution uses the modulo operator % to check if n is a divisor of 1162261467, the largest power of three (3^19) within the 32-bit signed integer range.
1162261467 % n == 0 is the key operation. The modulo operator calculates the remainder of the division of 1162261467 by n. If the result is 0, it implies that n divides the number evenly, indicating that n is a power of three. If the remainder is not 0, n is not a power of three because it does not divide the largest 32-bit power of three exactly.

The algorithm's efficiency lies in its O(1) time complexity since it requires a constant number of operations irrespective of the size of n. There is also O(1) space complexity, as no additional space is needed besides the input and the single boolean output. The pattern here is using a mathematical property of powers to avoid iteration or recursion, yielding an elegant and efficient solution.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with an example by determining if the number n = 27 is a power of three.

First, we verify that n is positive. Since 27 is greater than 0, we proceed to the next step.
We know that the largest power of three that can be contained in a 32-bit signed integer is 3^19, which is 1162261467.
We then perform the modulus operation with n and this number: 1162261467 % 27.
Calculating the modulus, we get 1162261467 % 27 = 0. Since there is no remainder, this operation confirms that 27 is a divisor of 1162261467.
Given the result of the modulus operation is zero, it indicates that 27 is a power of three, and therefore, our function should return true.

In this example, we've applied the provided solution to demonstrate that 27 is indeed a power of three. The steps are concise, avoiding the need for loops or recursion, and taking constant time to complete, which is an efficient way to reach the answer.

Solution Implementation

1class Solution:
2    def isPowerOfThree(self, number: int) -> bool:
3        # The largest power of 3 value that fits in a 32-bit signed integer is 3^19, which is 1162261467.
4        # If 'number' is a power of 3, it must divide 1162261467 without any remainder.
5        # 'number' must be positive since 0 and negative numbers cannot be powers of 3.
6      
7        # We check that the number is positive and that the modulo operation of 1162261467 by 'number' is zero.
8        # If the result is zero, 'number' is a divisor of 1162261467, implying it is a power of 3.
9        return number > 0 and 1162261467 % number == 0
10

1class Solution {
2    // Method to check if a number is a power of three
3    public boolean isPowerOfThree(int n) {
4        // 1162261467 is the maximum integer that is a power of three
5        // (it is 3^19, as 3^20 is bigger than int).
6        // If 'n' is a power of three, it must divide this number without a remainder.
7      
8        // The condition 'n > 0' ensures that 'n' is positive,
9        // because negative numbers and zero cannot be powers of three.
10        return n > 0 && 1162261467 % n == 0;
11    }
12}
13

1class Solution {
2public:
3    // Function to check if a given number is a power of three
4    bool isPowerOfThree(int n) {
5        // 1162261467 is the largest integer that is a power of three (3^19)
6        // If n is a power of three, it must be a divisor of 1162261467.
7      
8        // Check if n is positive and if 1162261467 is divisible by n
9        return n > 0 && 1162261467 % n == 0;
10    }
11};
12

1// Determines if the given number is a power of three.
2// Uses the largest power of three that fits in a 32-bit signed integer to check divisibility.
3// @param {number} n The number to check.
4// @returns {boolean} True if the number is a power of three, otherwise false.
5function isPowerOfThree(n: number): boolean {
6    // The constant is the highest power of three (3^19) that fits in a 32-bit signed integer.
7    const maxPowerOfThree: number = 1162261467;
8
9    // A number is a power of three if it is positive and the maximum power of three (3^19) is divisible by it.
10    return n > 0 && maxPowerOfThree % n === 0;
11}
12

Time and Space Complexity

Time Complexity

The time complexity of the provided code snippet is O(1). This is because the operation involves a single modulo operation, which is executed in constant time regardless of the value of n.

Space Complexity

The space complexity of the code is also O(1). The algorithm does not use any additional space that scales with the input size, as it only involves checking a condition on the input number n and a fixed integer 1162261467, which is the largest power of 3 that fits within the 32-bit signed integer range.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don’t know