MediumMathBrainteaserUpdated Sep 2026

319. Bulb Switcher

Asked at LinkedIn

Difficulty

Medium

Time

O(1)

Space

O(1)

Pattern

Math

Companies

1

Problem

There are n bulbs in a row, all switched off at the start. You then run n rounds. In round i, you toggle every i-th bulb: bulb i, bulb 2i, bulb 3i, and so on. Toggling means flipping the state — off becomes on, on becomes off.

After all n rounds finish, return how many bulbs are on.

You cannot simulate this when n is large, because the total number of toggles is about n log n. The trick is to think about one bulb at a time. Bulb k gets toggled once for every divisor of k, because round d touches it exactly when d divides k. A bulb ends up on only if it was toggled an odd number of times.

Which bulbs survive all the toggling

bulbsonoffoff012Final state after 3 rounds: bulb 1 on, bulbs 2 and 3offtoggles per bulb123count122Bulb 1 has 1 divisor, bulbs 2 and 3 have 2 divisorseach
With n = 3, only bulb 1 is toggled an odd number of times, so it is the only one left on.

Constraints

  • ●0 <= n <= 10^9

Examples

Example 1
Inputn = 3
Output1
WhyStart: [off, off, off]. Round 1 turns all on: [on, on, on]. Round 2 toggles bulb 2: [on, off, on]. Round 3 toggles bulb 3: [on, off, off]. Only bulb 1 is on, so the answer is 1.
Example 2
Inputn = 0
Output0
WhyThere are no bulbs, so nothing can be on.
Example 3
Inputn = 1
Output1
WhyRound 1 turns the single bulb on, and there are no more rounds. The answer is 1.

Asked At

1 companies
CompanyDifficulty
LinkedInMediumView all LinkedIn questions →

How to Think About It

1

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.

2

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.

3

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.

4

Count the perfect squares in 1..n: that is floor(sqrt(n)). For n = 10, the squares are 1, 4, 9 -> 3 bulbs on.

5

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).

Divisors pair up — except for squares

bulb k toggled once per divisor of kdivisors pair as (d, k/d)unpaired only when d = k/dso k is on iff k is a perfect squareThe whole problem reduces to counting perfect squaresn = 10 → squares 1, 4, 9answer = floor(sqrt(10)) = 3
Only perfect squares have an odd number of divisors, so the answer is the count of squares up to n.
ComplexityTime O(1)Space O(1)The answer is just the integer square root of n, so the cost is one square-root computation with no extra memory.

What Trips People Up in Real Interviews

1

Simulating the toggles. It shows you understand the statement but will time out — use a small simulation only to discover the pattern.

2

Saying "odd number of divisors" without explaining why that means perfect squares. The pairing argument is the proof the interviewer wants.

3

Floating-point sqrt on large inputs. Near perfect squares it can round the wrong way; use an integer square root or correct the result.

4

Forgetting that n = 0 should return 0.

Solution Code

O(1) time
from math import isqrt

def bulbSwitch(n):
    return isqrt(n)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(1) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.