Bulb Switcher
Medium
There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.
On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
Example 1:
If n = 3, the bulbs are initially [off, off, off].
After the first round, the bulbs are [on, on, on].
After the second round, the bulbs are [on, off, on].
After the third round, the bulbs are [on, off, off].
So you should return 1 because there is only one bulb that is on.
Example 2:
If n = 0, return 0.
Example 3:
If n = 1, return 1.
What is the most efficient algorithm to solve this problem? What is the time and space complexity of your solution?
Solution
Naive Solution
The naive solution involves simulating the process as described in the problem. We can use a boolean array to represent the bulbs, where true indicates the bulb is on and false indicates it is off. We iterate through the rounds, toggling the appropriate bulbs in each round, and finally count the number of bulbs that are on.
class Solution {
public int bulbSwitch(int n) {
boolean[] bulbs = new boolean[n];
for (int i = 1; i <= n; i++) {
for (int j = i - 1; j < n; j += i) {
bulbs[j] = !bulbs[j];
}
}
int count = 0;
for (boolean bulb : bulbs) {
if (bulb) {
count++;
}
}
return count;
}
}
Time Complexity: O(n^2), where n is the number of bulbs. The nested loops iterate up to n times each.
Space Complexity: O(n), due to the boolean array of size n.
Optimal Solution
Observe that a bulb is toggled once for each of its factors. For example, bulb 12 is toggled on rounds 1, 2, 3, 4, 6, and 12. A bulb will be on at the end if it is toggled an odd number of times. This happens if and only if the bulb number has an odd number of factors.
Numbers that are perfect squares have an odd number of factors. For example, 9 has factors 1, 3, and 9. Non-perfect squares have an even number of factors, because factors come in pairs (e.g., for 12, the pairs are (1, 12), (2, 6), and (3, 4)).
Therefore, the number of bulbs that are on at the end is equal to the number of perfect squares less than or equal to n. This is equal to the floor of the square root of n.
class Solution {
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}
Time Complexity: O(1), as Math.sqrt() is typically implemented using an efficient algorithm.
Space Complexity: O(1), as we use only constant extra space.
Edge Cases
- n = 0: The loop will not execute, and the count remains 0, which is the correct answer.
- n = 1: The square root of 1 is 1, so the answer is 1, which is the correct answer.
