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

• ``````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.

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

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

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