Power of Three


  • 0

    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


  • 1
    L

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

  • 0
    T
    This post is deleted!

  • 0
    L

  • 0
    G

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


  • 0
    L

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

  • 0

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


  • 0
    C

    good knowledge


  • 0
    U

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


  • 0
    B

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


  • 0
    Y

    @ bodziozet: you are not alone.


  • 0
    P

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


  • 0
    T

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


  • 0
    A

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

    }


Log in to reply
 

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