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.
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 returningfalse
. -
For positive values of
n
, the solution uses the modulo operator%
to check ifn
is a divisor of1162261467
, 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 of1162261467
byn
. If the result is0
, it implies thatn
divides the number evenly, indicating thatn
is a power of three. If the remainder is not0
,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 EvaluatorExample 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.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we