Two line solution using logarithms - works for all numbers (in predefined range), not just 32bit range


  • 1
    N
    public class Solution {
    
    private static final double epsilon = 10e-15;
    
    public boolean isPowerOfThree(int n) {
        
        double num = Math.log(n) / Math.log(3);
        
        return Math.abs((num - Math.round(num) )) <= epsilon;
        
    }
    }
    

    Why this works?

    Each number which is power of 3 can be written as

    n = 3^k

    if we multiply number with log we get

    log(n) = log(3^k)

    from that k goes out of the log

    log(n) = k * log(3)

    k = log(n) / log(3)

    k by the definition has to be positive whole number, so we check if this is true for log(n) / log(3) by subtracting this number from nearest whole number and we compare the result with some very small number (it is the way comparison looks like for double numbers)


  • 1

    "works for all numbers, not just 32bit range"

    Nah, doesn't even work for all numbers in 32bit range. Fails 1594322, for example.


  • 0
    N

    now it works :) Epsilon value was too big. However, this approach (maybe not the code itself) works for all numbers.


  • 0

    No it still doesn't work. Fails 14348906, for example.


  • 0
    N

    Ok, we can adjust epsilon as much as we want. Now it works for probably all numbers.


  • 0

    Now it might be correct inside 32bit range (I didn't test all possibilities), but it still fails for example 205891132094650, so at least your title claim is still wrong.


  • 0
    N

    As I have said already, this approach (not necessary the code itself) works for all numbers, you just have to adjust epsilon to be smaller in that cases!!!


  • 0

    Using a fixed epsilon like that, no matter how small, will leave exceptions.


  • 0
    N

    Why would it leave exceptions? If we take some range (0, n) there will always be possible to find epsilon which will be good enough for that range. This approach has problem that you need to change epsilon value each time, but it doesn't mean it doesn't work for all numbers (inside some range). With right epsilon you can cover any range you want, but of course outside that range it won't work. Okay, I'll change title works for any range if that sounds more right.


  • 0

    Ok, for a given capped range, I guess it can be made to work. It's just that "all numbers" makes me think of at least BigInteger (to stay with Java terms), which doesn't have such a cap.


  • 0
    N

    where does the magic number 10e-15 come from? how do you know the epsilon is small enough?


Log in to reply
 

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