Bulb Switcher

Problem#

n bulbs, all off. In round k (1-indexed), toggle every k-th bulb. After n rounds, how many bulbs are on?

Examples#

• n=3 → 1.
• n=0 → 0; n=1 → 1.

Constraints#

• 0 <= n <= 10^9.

Approach#

Bulb i is toggled once per divisor of i. It ends on iff that count is odd. A positive integer has an odd number of divisors iff it’s a perfect square (divisors pair as (d, i/d) except when d = i/d). So count perfect squares <= n: floor(sqrt(n)).

Solution#

class Solution {
public:
    int bulbSwitch(int n) {
        return (int)sqrt((double)n);
    }
};

func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n)))
}

import math

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(math.isqrt(n))

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

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

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

Editorial#

A pure number-theory collapse — the simulation would be O(n log n) but the closed form is O(1). The divisor-pairing argument is the standard proof that perfect squares uniquely have an odd divisor count.

Complexity#

• Time: O(1).
• Space: O(1).

Concept revision#

Related#

• Nim Game
• Power of Two