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.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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 > 0ensures 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 ifnis a divisor of1162261467, the largest power of three (3^19) within the 32-bit signed integer range. -
1162261467 % n == 0is the key operation. The modulo operator calculates the remainder of the division of1162261467byn. If the result is0, it implies thatndivides the number evenly, indicating thatnis a power of three. If the remainder is not0,nis 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.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
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
nis 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
nand 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
101class 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}
131class 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};
121// 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}
12In a binary min heap, the minimum element can be found in:
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 of the following is a good use case for backtracking?
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
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.