Description
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.
Examples:
Example 1:
Input: n = 27
Output: true
Explanation: 27 = 33
Example 2:
Input: n = 0
Output: false
Explanation: There is no x where 3x = 0.
Example 3:
Input: n = -1
Output: false
Explanation: There is no x where 3x = (-1).Solution in Python
To determine if a given integer n is a power of three, we need to check if there exists an integer x such that n=3x. If such an integer exists, then n is a power of three; otherwise, it is not.
Key Observations:
- Iterative Division Approach:
- If
nis a power of three, we can dividenby 3 repeatedly, and at the end, we should get 1. - If at any point
nis not divisible by 3 (i.e.,n % 3 != 0), thennis not a power of three.
- If
- Edge Cases:
- If
nis less than or equal to 0, it cannot be a power of three because powers of three are positive integers. - If
n = 1, it’s a power of three since 30=1.
- If
Python
class Solution:
def isPowerOfThree(self, n: int) -> bool:
# If n is less than or equal to 0, it cannot be a power of three
if n <= 0:
return False
# Repeatedly divide n by 3 while it is divisible by 3
while n % 3 == 0:
n //= 3
# If n becomes 1, then it was a power of three
return n == 1Explanation:
- Initial check for non-positive values:
- If
nis less than or equal to 0, returnFalsebecause powers of three are always positive integers.
- If
- Repeated division:
- While
nis divisible by 3, keep dividing it by 3 using the integer division operator//. This removes factors of 3 fromn.
- While
- Final check:
- If after all the divisions,
nbecomes 1, then the originalnwas a power of three. Otherwise, it wasn’t.
- If after all the divisions,
Solution in C++
C++
class Solution {
public:
bool isPowerOfThree(int n) {
// If n is less than or equal to 0, it cannot be a power of three.
if (n <= 0) return false;
// While n is divisible by 3, keep dividing n by 3.
// If after repeated division n becomes 1, it is a power of three.
while (n % 3 == 0) {
n /= 3;
}
// If n becomes 1, then it is a power of three. Otherwise, it's not.
return n == 1;
}
};Solution in Javascript
JavaScript
var isPowerOfThree = function(n) {
// Base case: if n is less than or equal to 0, it cannot be a power of three
if (n <= 0) return false;
// Keep dividing n by 3 as long as n is divisible by 3
while (n % 3 === 0) {
n /= 3; // Divide n by 3
}
// If after all divisions, n is reduced to 1, then it's a power of three
return n === 1;
};Solution in Java
Java
class Solution {
// Method to check if a number is a power of three
public boolean isPowerOfThree(int n) {
// Base condition: if n is less than or equal to 0, return false
// A number <= 0 cannot be a power of three
if (n <= 0) {
return false;
}
// Keep dividing n by 3 as long as the remainder is zero
// This checks if n is divisible by 3 until n becomes 1 (which means n was a power of 3)
while (n % 3 == 0) {
n /= 3; // Divide n by 3
}
// After the loop, if n becomes 1, it means n is a power of 3
// Otherwise, n is not a power of 3
return n == 1;
}
}