Math - Bulb Switcher

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

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

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)).

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