# Bulb Switcher
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/bulb-switcher)
Canonical: https://scaleengineer.com/dsa/problems/bulb-switcher
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture)
---
## Problem
There are `n` bulbs that are initially off. You first turn on all the bulbs, then you 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 `ith` round, you toggle every `i` bulb. For the `nth` round, you only toggle the last bulb.

Return _the number of bulbs that are on after `n` rounds_.

**Example 1:**

![](https://assets.glich.co/dsa/bulb-switcher/image0.jpg) 

**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:**

* `0 <= n <= 109`

# Approaches
## Brute Force Simulation
The most straightforward approach is to simulate the entire process. We create an array of n bulbs and toggle each bulb according to the rules for each round.
**Time:** O(n × n/1 + n × n/2 + ... + n × 1) ≈ O(n²) - For each round i, we toggle n/i bulbs, and the sum of n/i for i from 1 to n is approximately n × log(n), but the nested loops make it O(n²) · **Space:** O(n) - We need an array of size n to store the state of each bulb
**Pros:** Easy to understand and implement; Directly follows the problem description; Good for understanding the problem pattern
**Cons:** Very inefficient for large values of n; Will cause Time Limit Exceeded for n up to 10^9; Uses significant memory for large n
### Explanation
We simulate the entire bulb switching process by maintaining an array to track the state of each bulb. For each round i (from 1 to n), we toggle every i-th bulb. After all rounds, we count how many bulbs remain on.

```java
public int bulbSwitch(int n) {
    if (n == 0) return 0;
    
    boolean[] bulbs = new boolean[n];
    
    // Simulate each round
    for (int round = 1; round <= n; round++) {
        // Toggle every round-th bulb
        for (int i = round - 1; i < n; i += round) {
            bulbs[i] = !bulbs[i];
        }
    }
    
    // Count bulbs that are on
    int count = 0;
    for (boolean bulb : bulbs) {
        if (bulb) count++;
    }
    
    return count;
}
```

This approach directly implements the problem description. In round 1, we toggle all bulbs (turning them on). In round 2, we toggle every 2nd bulb. This continues until round n where we only toggle the n-th bulb.
### Algorithm
1. Create a boolean array of size n to represent bulbs (initially all false/off)
2. For each round i from 1 to n:
   - Toggle every i-th bulb (starting from position i-1)
3. Count the number of bulbs that are true (on)
4. Return the count

## Count Toggles Optimization
Instead of simulating the entire process, we can count how many times each bulb gets toggled. A bulb that is toggled an odd number of times will be on.
**Time:** O(n²) - For each of n bulbs, we check up to n potential divisors · **Space:** O(1) - We only use a few variables regardless of input size
**Pros:** No need to maintain bulb states; More efficient than simulation; Reveals the mathematical pattern
**Cons:** Still too slow for large n; Doesn't leverage the mathematical insight fully
### Explanation
Rather than maintaining the state of each bulb through all rounds, we can observe that a bulb's final state depends only on how many times it gets toggled. Since all bulbs start off, a bulb will be on if and only if it's toggled an odd number of times.

```java
public int bulbSwitch(int n) {
    int count = 0;
    
    // For each bulb position
    for (int i = 1; i <= n; i++) {
        int toggleCount = 0;
        
        // Count how many rounds toggle this bulb
        for (int round = 1; round <= i; round++) {
            if (i % round == 0) {
                toggleCount++;
            }
        }
        
        // If toggled odd number of times, it's on
        if (toggleCount % 2 == 1) {
            count++;
        }
    }
    
    return count;
}
```

Bulb i is toggled in round j if and only if j divides i evenly. So we count the divisors of each bulb position. If the count is odd, the bulb is on.
### Algorithm
1. Initialize count to 0
2. For each bulb position i from 1 to n:
   - Count the number of divisors of i
   - If the count is odd, increment the result count
3. Return the count

## Mathematical Solution - Perfect Squares
The key insight is that a bulb will be on if and only if it has an odd number of divisors. Only perfect squares have an odd number of divisors.
**Time:** O(1) - Computing square root is considered constant time · **Space:** O(1) - Only uses a single variable
**Pros:** Extremely efficient - constant time; Elegant mathematical solution; Works for any value of n within constraints; No memory overhead
**Cons:** Requires mathematical insight to understand; Not immediately obvious from problem description
### Explanation
The crucial observation is that bulb i is toggled once for each divisor of i. For most numbers, divisors come in pairs (d, i/d). However, perfect squares have an unpaired divisor (the square root), giving them an odd number of divisors.

```java
public int bulbSwitch(int n) {
    return (int) Math.sqrt(n);
}
```

Why does this work?
- Bulb i is toggled in round j if j divides i
- The number of times bulb i is toggled equals the number of divisors of i
- Most numbers have an even number of divisors (they come in pairs: if d divides n, then n/d also divides n)
- Perfect squares have an odd number of divisors because the square root pairs with itself
- Example: 16 has divisors {1, 2, 4, 8, 16}, but we can pair them as (1,16), (2,8), and 4 pairs with itself
- Therefore, only bulbs at perfect square positions (1, 4, 9, 16, ...) will be on
- The number of perfect squares ≤ n is floor(√n)
### Algorithm
1. Calculate the square root of n
2. Return the floor of the square root

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int bulbSwitch(int n) { return (int)sqrt(n); }
};

```

### Python

```python
class Solution:
    def bulbSwitch(self, n: int) -> int: return int(n ** (1 / 2))

```