273. Bulb Switcher
A row holds n light bulbs, numbered 1 through n, and every one of them starts off. You then run n rounds of switching:
- Round 1: flip every bulb.
- Round 2: flip every 2nd bulb (bulbs 2, 4, 6, …).
- Round
i: flip everyi-th bulb. - Round
n: flip only bulbn.
Flipping a bulb toggles it — on becomes off, off becomes on.
Your function receives the integer n and returns a single integer: the number of bulbs that are still on after round n finishes.
Example 1:
Input: n = 3
Output: 1
Explanation: Start [off, off, off]. Round 1 flips all three: [on, on, on]. Round 2 flips bulb 2: [on, off, on]. Round 3 flips bulb 3: [on, off, off]. Only bulb 1 is lit.
Example 2:
Input: n = 10
Output: 3
Explanation: Bulbs 1, 4, and 9 end up on — exactly the perfect squares up to 10.
Constraints:
- 0 ≤ n ≤ 10⁵
Hints:
Bulb b is flipped in round i exactly when i divides b. So its final state depends only on how many divisors b has: an odd count means on, an even count means off.
Divisors come in pairs d and b/d, which makes the count even — unless some pair collapses because d = b/d. For which numbers b does a divisor satisfy d * d = b?
Only perfect squares have an odd number of divisors, so the answer is the count of perfect squares in 1..n, which is floor(sqrt(n)).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3
Expected output: 1