// 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);
One Line Math Solution with some explanation


It should be O(1). Here is the answer from Quora: https://www.quora.com/WhatisthetimecomplexityofsqrtfunctionasdefinedintheC++mathlibrary

Nope. It should be O(1) because it is implemented using Newton method. https://www.quora.com/WhatisthetimecomplexityofsqrtfunctionasdefinedintheC++mathlibrary