Solution: Bulb Switcher

Statement▼

You are given n bulbs, all initially turned off. You perform n rounds of toggling operations:

In round $1$ , you turn on every bulb.
In round $2$ , you toggle every $2^{nd}$ bulb.
In round $3$ , you toggle every $3^{rd}$ bulb.
In general, during round i, you toggle every i-th bulb (turning it on if it is off, or turning it off if it is on).
In round n, you toggle only the last bulb.

Return the number of bulbs that remain on after all n rounds have been completed.

Constraints:

$0 \leq$ n $\leq 10^9$

The key insight is that a bulb at position $k$ is toggled once for every divisor of $k$ . A bulb remains on only if it has been toggled an odd number of times, which means $k$ must have an odd number of divisors. Divisors typically come in pairs: for any divisor ...

⋮

Tap here to switch tabs

Problem

Submissions

Solution

Home

Courses

Grokking the Coding Interview Patterns

Solution: Bulb Switcher

Statement▼

You are given n bulbs, all initially turned off. You perform n rounds of toggling operations:

In round $1$ , you turn on every bulb.
In round $2$ , you toggle every $2^{nd}$ bulb.
In round $3$ , you toggle every $3^{rd}$ bulb.
In general, during round i, you toggle every i-th bulb (turning it on if it is off, or turning it off if it is on).
In round n, you toggle only the last bulb.

Return the number of bulbs that remain on after all n rounds have been completed.

Constraints:

$0 \leq$ n $\leq 10^9$