# LeetCode 319: Bulb Switcher

## Problem Restatement

There are `n` bulbs in a row.

All bulbs are initially off.

We perform `n` rounds:

| Round | Operation |
|---:|---|
| `1` | Turn on every bulb |
| `2` | Toggle every second bulb |
| `3` | Toggle every third bulb |
| `i` | Toggle every `i`th bulb |
| `n` | Toggle only the `n`th bulb |

Return how many bulbs are on after all rounds. The official constraints are `0 <= n <= 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of bulbs left on |
| Initial state | All bulbs are off |
| Action | Toggle means off becomes on, and on becomes off |

Function shape:

```python
def bulbSwitch(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 3
```

Initial state:

```text
off off off
```

After round `1`:

```text
on on on
```

After round `2`:

```text
on off on
```

After round `3`:

```text
on off off
```

Only one bulb is on.

Output:

```python
1
```

Example 2:

```python
n = 0
```

There are no bulbs.

Output:

```python
0
```

Example 3:

```python
n = 1
```

There is one bulb.

Round `1` turns it on.

Output:

```python
1
```

## First Thought: Simulate the Rounds

We can create an array of `n` booleans.

Then for each round `i`, toggle every multiple of `i`.

```python
bulbs = [False] * n

for step in range(1, n + 1):
    for pos in range(step, n + 1, step):
        bulbs[pos - 1] = not bulbs[pos - 1]
```

This is correct for small `n`.

But `n` can be as large as `10^9`, so simulation is impossible.

We need to understand the final state directly.

## Key Insight

Look at one bulb.

Bulb `k` is toggled once for every round number that divides `k`.

For example, bulb `12` is toggled in rounds:

```text
1, 2, 3, 4, 6, 12
```

because those are exactly the divisors of `12`.

So the final state of bulb `k` depends on the number of divisors of `k`.

| Number of toggles | Final state |
|---:|---|
| Even | Off |
| Odd | On |

Since every bulb starts off, only bulbs toggled an odd number of times remain on.

## Why Perfect Squares Matter

Most divisors come in pairs.

For example, for `12`:

```text
1 * 12
2 * 6
3 * 4
```

That gives an even number of divisors.

But for a perfect square, one divisor pairs with itself.

For example, for `16`:

```text
1 * 16
2 * 8
4 * 4
```

The divisor `4` is counted only once.

So `16` has an odd number of divisors:

```text
1, 2, 4, 8, 16
```

Therefore:

| Bulb position | Final state |
|---|---|
| Perfect square | On |
| Not a perfect square | Off |

So the answer is the number of perfect squares less than or equal to `n`.

## Counting Perfect Squares

The perfect squares up to `n` are:

```text
1^2, 2^2, 3^2, ..., k^2
```

where:

```python
k * k <= n
```

The largest such `k` is:

```python
floor(sqrt(n))
```

So the answer is:

```python
floor(sqrt(n))
```

## Algorithm

1. Compute the integer square root of `n`.
2. Return it.

In Python, use:

```python
math.isqrt(n)
```

This returns the exact integer floor of the square root.

## Correctness

Bulb `k` is toggled exactly once for each divisor of `k`.

A bulb remains on exactly when it is toggled an odd number of times.

Every non-square integer has divisors that pair as `(a, k / a)`, so it has an even number of divisors.

Every perfect square has one unpaired divisor, its square root, so it has an odd number of divisors.

Therefore, exactly the bulbs at perfect-square positions remain on.

The number of perfect squares from `1` through `n` is `floor(sqrt(n))`.

So returning `math.isqrt(n)` gives exactly the number of bulbs left on.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | Integer square root is constant for fixed-size input constraints |
| Space | `O(1)` | No extra data structure is needed |

## Implementation

```python
import math

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

## Code Explanation

The whole problem reduces to counting perfect squares.

```python
math.isqrt(n)
```

returns the largest integer `x` such that:

```python
x * x <= n
```

That is exactly the number of perfect squares up to `n`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.bulbSwitch(0) == 0
    assert s.bulbSwitch(1) == 1
    assert s.bulbSwitch(2) == 1
    assert s.bulbSwitch(3) == 1
    assert s.bulbSwitch(4) == 2
    assert s.bulbSwitch(10) == 3
    assert s.bulbSwitch(16) == 4
    assert s.bulbSwitch(999999999) == 31622
    assert s.bulbSwitch(1000000000) == 31622

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `0` | No bulbs |
| `1` | First perfect square |
| `2`, `3` | Only bulb `1` remains on |
| `4` | Bulbs `1` and `4` remain on |
| `10` | Perfect squares are `1`, `4`, `9` |
| `16` | Includes `4^2` |
| Large inputs | Confirms no simulation |