# ** A summary of `all` solutions (new method included at 15:30pm Jan-8th)

• Well, this problem doesn't seem to be quite interesting or worthwhile to think about at a first glance. I had the same feeling at the beginning. However, after seeing a couple of posts, I saw a couple of interesting ways. So here is a summary post and hope you learn something from others' solutions.

Two trivial solutions first:
#Recursive Solution#

``````public boolean isPowerOfThree(int n) {
return n>0 && (n==1 || (n%3==0 && isPowerOfThree(n/3)));
}
``````

#Iterative Solution#

``````public boolean isPowerOfThree(int n) {
if(n>1)
while(n%3==0) n /= 3;
return n==1;
}
``````

my original code:
public boolean isPowerOfThree(int n) {
while(n>1) {
if(n%3!=0) return false;
n /= 3;
}
return n<=0 ? false : true;
}

Method 1

Find the maximum integer that is a power of 3 and check if it is a multiple of the given input. (related post)

``````public boolean isPowerOfThree(int n) {
int maxPowerOfThree = (int)Math.pow(3, (int)(Math.log(0x7fffffff) / Math.log(3)));
return n>0 && maxPowerOfThree%n==0;
}
``````

Or simply hard code it since we know `maxPowerOfThree = 1162261467`:

``````public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
``````

It is worthwhile to mention that Method 1 works only when the base is prime. For example, we cannot use this algorithm to check if a number is a power of 4 or 6 or any other composite number.

Method 2

If `log10(n) / log10(3)` returns an int (more precisely, a double but has 0 after decimal point), then n is a power of 3. (original post). But be careful here, you cannot use `log` (natural log) here, because it will generate round off error for `n=243`. This is more like a coincidence. I mean when `n=243`, we have the following results:

``````log(243) = 5.493061443340548    log(3) = 1.0986122886681098
==> log(243)/log(3) = 4.999999999999999

log10(243) = 2.385606273598312    log10(3) = 0.47712125471966244
==> log10(243)/log10(3) = 5.0
``````

This happens because `log(3)` is actually slightly larger than its true value due to round off, which makes the ratio smaller.

``````public boolean isPowerOfThree(int n) {
return (Math.log10(n) / Math.log10(3)) % 1 == 0;
}
``````

Method 3 related post

``````public boolean isPowerOfThree(int n) {
return n==0 ? false : n==Math.pow(3, Math.round(Math.log(n) / Math.log(3)));
}
``````

Method 4 related post

``````public boolean isPowerOfThree(int n) {
return n>0 && Math.abs(Math.log10(n)/Math.log10(3)-Math.ceil(Math.log10(n)/Math.log10(3))) < Double.MIN_VALUE;
}
``````

`Cheating` Method

This is not really a good idea in general. But for such kind of `power` questions, if we need to check many times, it might be a good idea to store the desired powers into an array first. (related post)

``````public boolean isPowerOfThree(int n) {
int[] allPowerOfThree = new int[]{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467};
return Arrays.binarySearch(allPowerOfThree, n) >= 0;
}
``````

or even better with HashSet:

``````public boolean isPowerOfThree(int n) {
HashSet<Integer> set = new HashSet<>(Arrays.asList(1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467));
return set.contains(n);
}
``````

#New Method Included at 15:30pm Jan-8th#

The idea is to convert the original number into radix-3 format and check if it is of format `10*` where `0*` means `k` zeros with `k>=0`.

``````public boolean isPowerOfThree(int n) {
return Integer.toString(n, 3).matches("10*");
}
``````

Any other interesting solutions?

If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java

• For all current math problems, it uses log or pow method. I think they are substantially recursive or iterative.
That is why I am feeling there might be some number theory (integer) without involving any double/float number. Hope someone could throw some light on it.

• Good post but one small mistake: (int)(Math.log(0x7fffffff)/Math.log(3)) does not give the maximum integer that is a power of 3, but Math.pow(3, (int)(Math.log(0x7fffffff)/Math.log(3))) does.

``````public boolean isPowerOfThree(int n) {
while(n>1) {
if(n%3!=0) return false;
n /= 3;
}
return n<=0 ? false : true;
}
``````

`return n<=0 ? false : true;` ? Am I having a bad dream? :-)

Also, you test both `n>1` and `n%3!=0` in every loop iteration. I think

``````public boolean isPowerOfThree(int n) {
if (n > 1)
while (n % 3 == 0)
n /= 3;
return n == 1;
}
``````

is not just more efficient but also clearer.

And I suggest

``````int maxPow3 = (int) Math.pow(3, (int)(Math.log(Integer.MAX_VALUE) / Math.log(3)));

public boolean isPowerOfThree(int n) {
return (n > 0) && (maxPow3 % n == 0);
}
``````

for the first math solution, this way its beauty is shown clearly. Maybe ZhaoMai wouldn't have missed it then.

Even lets you say "maxPow3" in the note instead of repeating a part of the expression and making the mistake that mach7 pointed out :-P

• in method 2, why we cannot use natural log? If natural log has round up problem, why it is not a problem for base 10 log? Or the base 10 log still has this problem, but because the test case is limited.

• it works with all base logs

• base e log has problem. one test case failed. I tried.

• Well, as you can tell, I have been writing `stupid` code :(

Thanks for pointing it out~

• It's interesting that C++ doesn't allow the similar code in method 2 but Java does. '%' needs integer in c++ and we can't do that due to our purpose.

• @兔拿 see my updated content with explanations. To be quick, this happens more like a coincidence.

• Well, now it's worse, being an infinite loop :-P
(for example for n=2)

• omg, my bad again... Have it fixed now.

• haha, folks really have many good ways to tackle the problem. I'll just bring up 2 cents.

Approach 1: Recursive

For n, if it is a power of 3, it falls into one of two cases:

(1) n = 3^2k = (3^k)2

(2) n = 3^2k+1 = (3k^)2 * 3

So, either check sqrt(n) or sqrt(n/3), recursively.
Time complexity is faster than being divided by 3.

C++ code:

``````bool isPowerOfThree(int n) {
if (n < 1) return false;
if (n == 1) return true;
int x = sqrt(n);
if (n == x * x)
return isPowerOfThree(x);
else {
if (n % 3 != 0) return false;
else return isPowerOfThree(n/3);
}
}
``````

Approach 2: Prime factors to filter

Use Sieve algorithm to find all prime numbers less than n. Then check if n can be divided by any non-3 prime number. If yes, return false.

If we cheat to provide the array of prime numbers without calling Sieve algorithm, the approach's time complexity is close to O(1). Code omitted.

• ``````public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}``````

• I am having a hard time calculating the run time of this. Can you help me how to figure out the run time of the iterative function? Many thanks!

• Hi, thanks for your post. but I am still wondering why it fail for other base.
As you mentioned, `log(3)` is larger than the trure value. but when I run the test: `log10(3)/log(exp(1)) - log(3) == 0` it return true.
also it that mean log2(3) is not so accurate as log10(3)?

• I used

``````        double p = Math.log(n) / Math.log(3);
if (Math.abs(p - Math.round(p)) <= Math.ulp(p))
``````

to judge whether the log3(n) is a integer or not. That is because java doc has following description about Math.log function

``````The computed result must be within 1 ulp of the exact result.
``````

• Is there any guarantee that the division and subtraction results will also be within one ULP? I find this method somewhat risky. Better to check with a greater tolerance (that can be found out experimentally).

• The whole logic about using log10 or log or whatever, or whether it gives true result or not, is really implementation-specific. And probably hardware-specific too as I don't see any requirements in the API docs for the implementation to use the `strictfp` keyword. Moreover, it explicitly states

Unlike some of the numeric methods of class StrictMath, all
implementations of the equivalent functions of class Math are not
defined to return the bit-for-bit same results. This relaxation
permits better-performing implementations where strict reproducibility
is not required.

So you'd have to use `StrictMath` to get portable results. Otherwise it's just a matter of luck. Or use some reasonable tolerance instead (which can be determined experimentally with some safety margin too).

• What do you think about "Method 3", though? Don't you think it's safe?

Also, I don't think StrictMath is a good suggestion. Yes, it has reproducibility, but reproducibly computing wrong values is still bad.

I tested both on ideone, where

``````import java.lang.*;

class Ideone {
public static void main (String[] args) {
for (int e=0, p=1; e<20; e++, p*=3) {
boolean m =       Math.log(p) /       Math.log(3) == e;
boolean s = StrictMath.log(p) / StrictMath.log(3) == e;
System.out.println(e + ": " + m + " " + s + " " + p);
}
}
}
``````

gives this output:

``````0: true true 1
1: true true 3
2: true false 9
3: true false 27
4: true false 81
5: false true 243
6: true false 729
7: true false 2187
8: true false 6561
9: true false 19683
10: false true 59049
11: true false 177147
12: true false 531441
13: false false 1594323
14: true false 4782969
15: false false 14348907
16: true false 43046721
17: false true 129140163
18: true false 387420489
19: true false 1162261467
``````

You can see `Math` even was lucky way more often than `StrictMath` was.

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