Eight different solutions with comments


  • 1
    //AC - direct iterative method;
    bool isPowerOfThree(int n)
    {
        long a = 1;
        while(a <= n)
        {
            if(a==n)
                return true;
            a *= 3;
        }
        return false;
    }
    

    recursive solution

        bool isPowerOfThree(int n)
        {
            return n>0 && 1162261467%n==0;
        }
    

    //AC - the following four methods are using mod;
    //This process can be faster using hashmap or binary search;
    bool isPowerOfThree(int n)
    {
        return (n == 1 || n == 3 || n == 9 || n == 27 || n == 81 || n == 243 || n == 729 || n == 2187 || n == 6561 || n == 19683 || n == 59049 || n == 177147 || n == 531441 || n == 1594323 || n == 4782969 || n == 14348907 || n == 43046721 || n == 129140163 || n == 387420489 || n == 1162261467);
    }
    
    bool isPowerOfThree(int n)
    {
        int maxPowerOfThree = (int)pow(3, (int)(log(INT_MAX)/log(3)));
        return n>0 && maxPowerOfThree%n==0;
    }
    
    bool isPowerOfThree(int n)
    {
        return n>0 && (int)pow(3, 19)%n==0;
    }
    
    bool isPowerOfThree(int n)
    {
        return n>0 && 1162261467%n==0;
    }
    

    //AC - the following two methods are using log;
    bool isPowerOfThree(int n)
    {
        return fmod(log10(n)/log10(3), 1) == 0;
    }
    
    bool isPowerOfThree(int n)
    {
        double ret = log10(n)/log10(3);
        return ret==(int)ret;
    }

  • 0
    A

    Try for n =2. OJ gave error for this test case.


  • 0

    Sorry to reply this late, I re-checked it and as for n=2 case the ret=log10(n)/log10(3)=0.630930 while (ret)=0 and quite clearly the equation is not equal so return false which means n=2 is not the power of three. Something wrong about this? I hope this can help. B.T.W. this technique has some mathematical logic behind, maybe you should do some reasoning to understand it.


  • 0
    O

    I don't quite understand your code

    bool isPowerOfThree3(int n)
    {
        return n>0 && (int)pow(3, 19)%n==0;
    }
    
    bool isPowerOfThree4(int n)
    {
        return n>0 && 1162261467%n==0;
    }
    

    why you use pow(3, 19)%n here? Thx


  • 0

    In the assistance of the OJ, you can easily get it that the 19 is the biggest exponent of 3 which means here pow(3, 19) == 1162261467. B.T.W. you should post this question in comment section instead of answer.


  • 0
    O

    thanks for explanation


Log in to reply
 

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