Bulb Switcher

Bulb Switcher

What is this problem about?

The Bulb Switcher interview question is a famous brainteaser. You start with n bulbs that are all off. You perform n rounds of switching. In the i-th round, you toggle every i-th bulb. The goal is to find how many bulbs remain ON after n rounds. This Bulb Switcher coding problem is more about mathematical deduction than complex data structures.

Why is this asked in interviews?

Companies like Microsoft and Amazon use this to see if a candidate can look past the simulation and find an underlying mathematical pattern. It tests your ability to think critically about factors and divisors. Most interviewers don't actually want you to simulate the toggling; they want you to realize the "Perfect Square" property.

Algorithmic pattern used

This utilizes the Brainteaser, Math interview pattern. A bulb at position x is toggled once for every divisor of x. For example, bulb 6 is toggled at rounds 1, 2, 3, and 6 (4 times). Since 4 is even, it ends up OFF. Only numbers with an odd number of divisors remain ON. Mathematically, only perfect squares have an odd number of divisors. Thus, the problem reduces to counting the perfect squares up to n, which is simply floor(sqrt(n)).

Example explanation

Let n = 5.

1. Round 1: Toggle all. Bulbs: [ON, ON, ON, ON, ON]
2. Round 2: Toggle 2, 4. Bulbs: [ON, OFF, ON, OFF, ON]
3. Round 3: Toggle 3. Bulbs: [ON, OFF, OFF, OFF, ON]
4. Round 4: Toggle 4. Bulbs: [ON, OFF, OFF, ON, ON]
5. Round 5: Toggle 5. Bulbs: [ON, OFF, OFF, ON, OFF] Only bulbs 1 and 4 are ON. Both are perfect squares (1^2 and 2^2). Answer: 2.

Common mistakes candidates make

• Simulating the rounds: Attempting to use a boolean array and nested loops (O(N^2)). This will fail for large values of n.
• Overcomplicating the math: Trying to use prime factorization to count divisors when the property of perfect squares is much more direct.
• Precision issues: Not handling the square root calculation correctly for very large integers in languages like C++ or Java.

Interview preparation tip

When you see a problem involving toggling states based on multiples or factors, investigate the properties of divisors. Many such problems boil down to whether a number has an even or odd number of factors.