Java O(1) solution, for real - no bs :) No sqrt


  • 6
    A
    public int bulbSwitch(int n) {
        return (int) Math.pow(2, 0.5 * (Math.log(n)/Math.log(2)));
    }
    

    There is a Math trick to get a rounded to the floor square root of a number (this is exactly what we need since integers get rounded down).

    1. We can express sqrt(n) as n^0.5,
    2. then add a log trick: 2^log(base 2)(n^0.5),
    3. then simplify a little: 2^(0.5*log(base 2)(n)).
    4. Since java's Math library doesn't have log(base 2), we can get it by log(base e)(n) / log(base e)(2).

    I looked at Java's Math source code and its log method defaults to the log method of StrictMath. I have a link here for the StrictMath source:

    http://developer.classpath.org/doc/java/lang/StrictMath-source.html

    The log method is O(1) (I didn't see any loops or recursive calls), although extremely ugly, there is a lot going on in it, and I don't understand most of it :) Another slow-down comes from the pow method, it's also O(1) and even uglier than log :D

    I also ran a quick speed test for both sqrt and log versions of the bulbSwitch, here are the results ( I ran a few times, the results are relatively consistent) :

    bulbSwitchSqrt(5) ------------------------- 35437 ns
    bulbSwitchLog(5) -------------------------- 8495 ns
    bulbSwitchSqrt(25789104) ------------------ 421 ns
    bulbSwitchLog(25789104) ------------------- 822 ns
    

    For very small numbers log method is an order of the magnitude faster than sqrt, for very large numbers they are about the same. From what I read in the source code comments, small values require more precision, so there is more computation going on in both log and sqrt, otherwise sqrt is surprisingly fast.

    I am not making any claims here, just sharing what I've found out :) Let me know if I made a mistake somewhere or missed anything.

    Cheers.


  • 1
    S

    log might be O(1) but what about Math.pow? No way it runs in O(1)


  • -1
    A

    Check out this http://developer.classpath.org/doc/java/lang/StrictMath-source.html source, and look for the pow method. I am either blind or there is no linear-sublinear complexity there after all. It's very likely that I am blind :)


Log in to reply
 

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