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

- We can express sqrt(n) as n^0.5,
- then add a log trick: 2^log(base 2)(n^0.5),
- then simplify a little: 2^(0.5*log(base 2)(n)).
- 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.