Solution
This is a pretty trivial question and definitely not a good interview question. All we have to do is return the square root of the number n. That is because -
A bulb ends up on if and only if it is switched an odd number of times. Bulb i is switched in round d if and only if d divides i. So bulb i ends up on if and only if it has an odd number of divisors.
Divisors come in pairs, like i=12 has divisors 1 and 12, 2 and 6, and 3 and 4. Except when i is a square, like 36 has divisors 1 and 36, 2 and 18, 3 and 12, 4 and 9, and double divisor 6. So bulb i ends up on if and only if i is a square.
sqrt(n) gives you the root of the largest square in the range [1,n]. And 1 is the smallest root. So you have the roots from 1 to sqrt, that’s sqrt many roots.
int bulbSwitch(int n) {
return sqrt(n);
}
Time complexity: O(n)