Bulb Switcher

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

Algorithms Math

Initially n bulbs are off. In round i, toggle every ith bulb. After n rounds, count bulbs that are on.

Input: n=3 → Output: 1

Input: n=0 → Output: 0

Solution Approach

A bulb i is toggled for each divisor of i. It ends on only if toggled an odd number of times, which means i is a perfect square.

Only perfect squares have odd number of divisors (the square root is counted once).
Answer = floor(sqrt(n)).

Java

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