// 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);
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.
It should be O(1). Here is the answer from Quora: https://www.quora.com/What-is-the-time-complexity-of-sqrt-function-as-defined-in-the-C++-math-library
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.