# One Line Math Solution with some explanation

• ``````// For prime numbers, they must be off because we can reach them only twice (The first round and their own round).
/* For other numbers, if we can reach them odd times, then they are on; otherwise, they are off. So only
those numbers who have square root will be reached odd times and there are sqrt(n) of them because
for every x > sqrt(n), x*x > n and thus should not be considered as the answer. */

return (int)sqrt(n);``````

• This post is deleted!

• This is actually O(logn) time complexity not O(1).

• Yep, u r right. Thank you for pointing out my mistake! :-)

• Isn't Newton's method close to O(1) since we do not need precision (we're rounding to an integer). I'm not sure if sqrt uses Newton's or not.

• Ok. Let me check the source code and give u feedback later.

• Nope. It should be O(1) because it is implemented using Newton method. https://www.quora.com/What-is-the-time-complexity-of-sqrt-function-as-defined-in-the-C++-math-library

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