# Power of Three

• In this article we will look into ways of speeding up simple computations and why that is useful in practice.

• 4 is neat. A different kind of smart-dumb solution analyzing numeric constraints is to see we have only 20 possibilities:

``````public class Solution {
public boolean isPowerOfThree(int n) {
switch(n) {
case 1:
case 3:
case 9:
case 27:
case 81:
case 243:
case 729:
case 2187:
case 6561:
case 19683:
case 59049:
case 177147:
case 531441:
case 1594323:
case 4782969:
case 14348907:
case 43046721:
case 129140163:
case 387420489:
case 1162261467:
return true;
default: return false;
}
}
}
``````

• This post is deleted!

• instead of epsilon why not use Java.lang.Math.round like this (n == Math.pow(3, (int)(Math.round(Math.log(n) / Math.log(3)))));

• I'm wondering how the epsilon method could work on C++. The following code won't work for n=243.

``````    bool isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
double EPSILON = numeric_limits<double>::epsilon();
double l = log(double(n)) / log(double(3));
double f = fmod(l + EPSILON, 1);
return f <= 2 * EPSILON;
}
``````

• Approach #4 is nice, but not quite applicable for languages that support arbitrary large number, like Python.

• good knowledge

• since there are only 19 integer that are power of 3, why don't we build a hashset, get the value from the hashset?

• Hi. Because English is not my native language I fail miserably to understand the question. I was thinking for sure that the objective was to find if number n can be described as x^3. Find if n = x^3 :). I'm curious if the only one:)

• @ bodziozet: you are not alone.

• I like that the naive approach is actually the fastest if you can't do the fast approach (if you need to handle arbitrarily sized inputs).

• 4 different C++ solutions:

/* too hacky solution 1:
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0)
return false;
int i = 1;
while (i < n && (i < (2147483647 / 3))) { // add compare with 2147483647 to avoid int overflow
i *= 3;
}

``````    return i == n;
}
``````

};*/

/* better solution 2, using long type i
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0)
return false;
long i = 1;
while (i < n) {
i *= 3;
}

``````    return i == n;
}
``````

}; */

/* even better solution 3, using division instead of multiplication
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0)
return false;

``````    while (n % 3 == 0) {
n /= 3;
}

return n == 1;
}
``````

}; */

/* Solution 4, without loop, O(1) */
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0)
return false;
const int Max3PowerInt = 1162261467; // 3^19
return Max3PowerInt % n == 0;
}
};

• The following recursive solution is also available, which can be seen as a variant of Java Approach #1 (Naive):

class Solution {
public boolean isPowerOfThree(int n) {

``````    return (n == 1) || isPowerOfThree((double)(n));
}

private boolean isPowerOfThree(double d) {

if (d / 3 == 1.0)
return true;
else if (d / 3 < 1.0)
return false;
else
return isPowerOfThree(d / 3);
}
``````

}

• Regarding solution #4, it seems like this method can be applied to any prime number.

• Why do some people say solution 4 only works on prime numbers? What if the base number is not prime? I think it works on all positive integers.

• @FanBu If we wanted to see if a number n was a power of a number m, the same approach would work for m = { any prime number }.

Example of it NOT working for a non-prime: We want to see if some number n is a power of 8. Largest power of 8 that fits into a 32-bit signed int is 8^10 = 1,073,741,824. We can choose n=2, n=16, n=32 and many other numbers that would evaluate to true but are not powers of 8.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.