Bulb Switcher

MediumMathmath

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n bulbs in a row, numbered 1 to n, all initially off. You make n passes. On pass i (for i = 1, 2, ..., n) you toggle every bulb whose number is a multiple of i: off becomes on and on becomes off. Return how many bulbs are on after all n passes. n can be as large as 10^9, so simulating is too slow; look for a closed form.

Examples

Input: n = 3
Output: 1
After pass 1 all are on; pass 2 turns bulb 2 off; pass 3 turns bulb 3 off. Only bulb 1 stays on.
Input: n = 0
Output: 0
There are no bulbs.

Constraints

  • 0 <= n <= 10^9
  • Bulbs are numbered from 1 to n
  • All bulbs start off

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More math problems