Bulb Switcher

medium math brainteaser

Problem

There are n bulbs, all initially OFF. On round i (1-indexed), you toggle every i-th bulb. After n rounds, how many bulbs are ON?

Inputn = 9

Output3

Bulbs 1, 4, 9 — the perfect squares ≤ 9.

def bulb_switch(n):
    return int(n ** 0.5)

function bulbSwitch(n) {
  return Math.floor(Math.sqrt(n));
}

class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

int bulbSwitch(int n) {
    return (int) sqrt((double) n);
}

Explanation

The whole solution is one line: int(n ** 0.5). That surprising shortcut comes from thinking about how many times each bulb gets toggled.

Bulb number i is flipped on round r exactly when r divides i. So a bulb ends up ON only if it was toggled an odd number of times, which means i must have an odd number of divisors.

Divisors normally come in pairs (like 2 and 6 for 12), so the count is usually even. The only numbers with an odd divisor count are perfect squares, because their square root pairs with itself.

Therefore the answer is just how many perfect squares are <= n, and that count is floor(sqrt(n)).

Example: n = 9. The perfect squares up to 9 are 1, 4, 9 — three of them. And indeed floor(sqrt(9)) = 3, so we return 3 without simulating anything.

Time: O(1) Space: O(1)