319. Bulb Switcher

Time: O(1)

Space: O(1)

Intuition

Bulb i is toggled by all its divisors. A bulb ends ON only if it has an odd number of divisors - which happens only for perfect squares. Count of perfect squares <= n = floor(âˆšn).

Algorithm

1Return (int)Math.Sqrt(n).

Example Walkthrough

Input: n = 3

1.Perfect squares <= 3: 1. floor(âˆš3)=1.
2.Only bulb 1 stays on.

Output: 1

Common Pitfalls

•Use integer square root carefully - floating point sqrt(4) might give 1.9999... for some n.

319.cs

// Approach: Only perfect-square positions have an odd number of divisors
// and remain on after all toggles; return floor(√n).
// Time: O(1) Space: O(1)

public class Solution
{
    public int BulbSwitch(int n)
    {
        return (int)Math.Sqrt(n);
    }
}

Was this solution helpful?