Bulb Switcher
Asked at LinkedIn
Problem
Bulb Switcher describes n bulbs that start off; in round i you toggle every i-th bulb, for rounds 1 through n. How many bulbs are on at the end? Simulating is too slow for large n — the interviewer wants you to find the number-theory pattern.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all LinkedIn questions → |
How to Think About It
Simulation toggles about n/1 + n/2 + ... + n/n bulbs, which is O(n log n) — too slow when n is up to 10^9.
Bulb k is toggled once for every divisor of k (round d touches it when d divides k). It ends up on iff it is toggled an odd number of times.
Key insight: divisors come in pairs (d, k/d). The only time a divisor is unpaired is when d == k/d, i.e. k is a perfect square. So only perfect-square bulbs have an odd divisor count.
Count the perfect squares in 1..n: that is floor(sqrt(n)). For n = 10, the squares are 1, 4, 9 -> 3 bulbs on.
Implementation detail: use an exact integer square root (isqrt) rather than floating-point sqrt to avoid rounding errors near large perfect squares.
Optimal Approach
Step 1: Observe that bulb k is toggled once per divisor of k.
Step 2: Divisors pair up as (d, k/d), except when k is a perfect square.
Step 3: So exactly the perfect-square bulbs end up on.
Step 4: Return the number of perfect squares <= n, which is floor(sqrt(n)).
Time: O(1) (or O(log n) for an exact integer square root). Space: O(1).
What Trips People Up in Real Interviews
Simulating the toggles. It shows you understand the statement but will time out — use a small simulation only to discover the pattern.
Saying "odd number of divisors" without explaining why that means perfect squares. The pairing argument is the proof the interviewer wants.
Floating-point sqrt on large inputs. Near perfect squares it can round the wrong way; use an integer square root or correct the result.
Forgetting that n = 0 should return 0.
Solution Code
from math import isqrt
def bulbSwitch(n):
return isqrt(n)Frequently Asked Questions
What is the Bulb Switcher problem?
Bulb Switcher describes `n` bulbs that start off; in round `i` you toggle every `i`-th bulb, for rounds 1 through `n`. How many bulbs are on at the end? Simulating is too slow for large `n` — the interviewer wants you to find the number-theory pattern.
How do you solve Bulb Switcher?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Bulb Switcher?
Bulb Switcher is asked at LinkedIn. It is a medium difficulty problem.
What are common mistakes on Bulb Switcher?
- Simulating the toggles. It shows you understand the statement but will time out — use a small simulation only to discover the pattern.
- Saying "odd number of divisors" without explaining why that means perfect squares. The pairing argument is the proof the interviewer wants.
- Floating-point `sqrt` on large inputs. Near perfect squares it can round the wrong way; use an integer square root or correct the result.
- Forgetting that `n = 0` should return 0.