In this article we will look into ways of speeding up simple computations and why that is useful in practice.
Click here to see the full article post
In this article we will look into ways of speeding up simple computations and why that is useful in practice.
Click here to see the full article post
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;
}
}
}
@tianyicai2010 Exponential means complex and expensive ( https://en.wikipedia.org/wiki/Category:SAT_solvers ).
Undecidable means impossible ( https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Undecidable_problem ).
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;
}
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);
}
}
@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.