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


  • 257
    E

    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#

    update following Stefan's answer below:

    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;
    }

    #It's all about MATH...#

    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#

    Radix-3 original post

    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


  • 0
    Z

    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.


  • 0
    M

    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.


  • 13

    About this one of yours:

    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


  • 0

    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.


  • 0
    A

    it works with all base logs


  • 0

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


  • 0
    E

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

    Thanks for pointing it out~


  • 0
    T

    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.


  • 0
    E

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


  • 0

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


  • 0
    E

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


  • 1
    P

    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.


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

  • 0
    A

    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!


  • 0
    L

    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)?

    Thanks in advance!


  • 0
    L

    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.
    

  • 0

    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).


  • 0

    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).


  • 0

    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.


Log in to reply
 

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