# LC 319. Bulb Switcher

### [Problem link](https://leetcode.com/problems/bulb-switcher/)

###### tags: `leedcode` `python` `medium`

There are <code>n</code> bulbs that are initially off. You first turn on all the bulbs, thenyou turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the <code>i^th</code> round, you toggle every <code>i</code> bulb. For the <code>n^th</code> round, you only toggle the last bulb.

Return the number of bulbs that are on after <code>n</code> rounds.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/bulb.jpg" style="width: 421px; height: 321px;" />

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.

**Example 2:**

Input: n = 0
Output: 0

**Example 3:**

Input: n = 1
Output: 1

**Constraints:**

- <code>0 <= n <= 10⁹</code>

## Solution 1 - Math

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

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(1) | O(1) |

## Note
Suppose there are 8 bulbs.

| round\bulb No. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| -------------- | -- | -- | -- | -- | -- | -- | -- | -- |
| 1 | ⚪ | ⚪ | ⚪ | ⚪ | ⚪ | ⚪ | ⚪ | ⚪ |
| 2 | ⚪ | ⚫ | ⚪ | ⚫ | ⚪ | ⚫ | ⚪ | ⚫ |
| 3 | ⚪ | ⚫ | ⚫ | ⚫ | ⚪ | ⚪ | ⚪ | ⚫ |
| 4 | ⚪ | ⚫ | ⚫ | ⚪ | ⚪ | ⚪ | ⚪ | ⚪ |
| 5 | ⚪ | ⚫ | ⚫ | ⚪ | ⚫ | ⚪ | ⚪ | ⚪ |
| 6 | ⚪ | ⚫ | ⚫ | ⚪ | ⚫ | ⚫ | ⚪ | ⚪ |
| 7 | ⚪ | ⚫ | ⚫ | ⚪ | ⚫ | ⚫ | ⚫ | ⚪ |
| 8 | ⚪ | ⚫ | ⚫ | ⚪ | ⚫ | ⚫ | ⚫ | ⚫ |

No.2 bulb will be switched once in round1, 2$~~~~~~~~~~~~~~~~~$-> light off
No.4 bulb will be switched once in round1, 2, 4$~~~~~~~~~~~~~$-> light on
No.6 bulb will be switched once in round1, 2, 3, 6$~~~~~~~~~~$-> light off

factor set of 2 : {1, 2}
factor set of 4 : {1, 2, 4}
factor set of 6 : {1, 2, 3, 6}

So if bulb No. is a perfect square, the bulb will be on in the end.

So we need to find out how many perfect square numbers in [1, n].
=> **int(sqrt(n))**

p.s. sqrt(8) = 2.82842 means $1^2$ and $2^2$ is less than or equal to 8.