Skip to main content

319. Bulb Switcher

medium

n bulbs start off. In round i, you toggle every i-th bulb. After n rounds, how many bulbs are on? The answer is floor(sqrt(n)) — a beautiful number-theory observation about perfect-square divisor counts.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Return the number of bulbs that are on after n rounds.

Constraints

  • 0 <= n <= 10^9

Examples

Example 1

Input
n = 3
Output
1

Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1, because there is only one bulb is on.

Example 2

Input
n = 0
Output
0

Example 3

Input
n = 1
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Bulb k is toggled once per divisor of k. So bulb k ends up ON iff k has an odd number of divisors.

Hint 2

Divisors come in pairs (d, k/d) — except when d == k/d, i.e., when k is a perfect square.

Hint 3

So bulbs at perfect-square positions (1, 4, 9, 16, ...) end up on; all others are off.

Hint 4

Count of perfect squares <= n is floor(sqrt(n)).

Solution approach

Reveal approach

The key observation: bulb k is toggled exactly once per divisor of k. Bulb k ends on if and only if it has an odd number of divisors. Divisors normally pair up (d, k/d), so the count is even — UNLESS the pair collapses to a single divisor when d == k/d, i.e., d^2 == k, i.e., k is a perfect square. Perfect squares are the only numbers with an odd divisor count. So the answer is the count of perfect squares in [1, n], which is floor(sqrt(n)). One line: return int(sqrt(n)). O(1) time and space. Simulation would be O(n^2) or O(n log n) and times out for n = 10^9.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • math
  • number-theory

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Bulb Switcher and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →