Problem Description

You have n bulbs arranged in a row, all initially turned off. You perform n rounds of operations on these bulbs.

In each round:

• Round 1: Turn on all bulbs
• Round 2: Toggle every 2nd bulb (turn it off if it's on, turn it on if it's off)
• Round 3: Toggle every 3rd bulb
• Round i: Toggle every i-th bulb
• Round n: Toggle only the last bulb

After completing all n rounds, you need to determine how many bulbs remain on.

Key insight: A bulb at position k gets toggled in round d if and only if d is a divisor of k. For example, bulb 6 gets toggled in rounds 1, 2, 3, and 6 (since these are all divisors of 6).

Since each bulb starts off, it will be on after all rounds if it's toggled an odd number of times, which happens when the bulb's position has an odd number of divisors. Only perfect square numbers have an odd number of divisors (because for perfect squares, one divisor pairs with itself).

Therefore, the problem reduces to counting how many perfect squares exist from 1 to n, which equals ⌊√n⌋.

Intuition

Let's trace through what happens to each bulb. Take bulb #6 as an example:

• Round 1: Turned ON (divisible by 1)
• Round 2: Turned OFF (divisible by 2)
• Round 3: Turned ON (divisible by 3)
• Round 6: Turned OFF (divisible by 6)

The pattern becomes clear: bulb #6 is toggled in rounds 1, 2, 3, and 6 - exactly when the round number divides 6. These are the divisors of 6.

This leads to a crucial observation: a bulb ends up ON if and only if it's toggled an odd number of times, since it starts OFF.

So which numbers have an odd number of divisors? Let's think about how divisors work. For most numbers, divisors come in pairs. For 12: (1,12), (2,6), (3,4) - that's 6 divisors total, an even count.

But perfect squares are special! For 16: (1,16), (2,8), (4,4). Wait - the divisor 4 pairs with itself! So we actually have divisors 1, 2, 4, 8, 16 - that's 5 divisors, an odd count.

This happens because when d × d = n, the divisor d only counts once, not twice. This is unique to perfect squares.

Therefore, only bulbs at positions that are perfect squares (1, 4, 9, 16, 25, ...) will remain ON. The question becomes: how many perfect squares are there from 1 to n?

The answer is simply ⌊√n⌋. For example, if n = 10, the perfect squares are 1, 4, and 9, which is exactly ⌊√10⌋ = 3 bulbs that remain on.

Solution Approach

Based on our mathematical analysis, we've established that only bulbs at perfect square positions remain on after all rounds. The implementation is remarkably elegant:

Direct Mathematical Solution:

Since we need to count perfect squares from 1 to n, we can directly compute this as ⌊√n⌋.

The implementation steps are:

1. Calculate the square root of n
2. Take the floor of this value (convert to integer)
3. Return this count

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(sqrt(n))

Why this works:

• If n = 10, the perfect squares ≤ 10 are: 1, 4, 9

• √10 ≈ 3.16, and ⌊3.16⌋ = 3

• This correctly gives us 3 bulbs that remain on

• If n = 25, the perfect squares ≤ 25 are: 1, 4, 9, 16, 25

• √25 = 5, and ⌊5⌋ = 5

• This correctly gives us 5 bulbs that remain on

Time and Space Complexity:

• Time Complexity: O(1) - We're performing a single mathematical operation
• Space Complexity: O(1) - No additional space is used

The beauty of this solution lies in transforming what appears to be a simulation problem requiring O(n²) operations into a simple O(1) mathematical calculation. By recognizing the pattern that only perfect squares have an odd number of divisors, we bypass the need to simulate the entire toggling process.

Example Walkthrough

Let's walk through a small example with n = 6 bulbs to understand the solution approach.

Initial state: All 6 bulbs are OFF: [OFF, OFF, OFF, OFF, OFF, OFF]

Now let's trace what happens to each bulb position through all rounds:

Bulb #1 (position 1):

• Round 1: Toggled ON (1 divides 1)
• Final state: ON (toggled 1 time - odd)

Bulb #2 (position 2):

• Round 1: Toggled ON (1 divides 2)
• Round 2: Toggled OFF (2 divides 2)
• Final state: OFF (toggled 2 times - even)

Bulb #3 (position 3):

• Round 1: Toggled ON (1 divides 3)
• Round 3: Toggled OFF (3 divides 3)
• Final state: OFF (toggled 2 times - even)

Bulb #4 (position 4):

• Round 1: Toggled ON (1 divides 4)
• Round 2: Toggled OFF (2 divides 4)
• Round 4: Toggled ON (4 divides 4)
• Final state: ON (toggled 3 times - odd)

Bulb #5 (position 5):

• Round 1: Toggled ON (1 divides 5)
• Round 5: Toggled OFF (5 divides 5)
• Final state: OFF (toggled 2 times - even)

Bulb #6 (position 6):

• Round 1: Toggled ON (1 divides 6)
• Round 2: Toggled OFF (2 divides 6)
• Round 3: Toggled ON (3 divides 6)
• Round 6: Toggled OFF (6 divides 6)
• Final state: OFF (toggled 4 times - even)

Final result: [ON, OFF, OFF, ON, OFF, OFF]

Notice that only bulbs #1 and #4 remain ON. These are at positions 1 and 4, which are perfect squares (1² = 1 and 2² = 4).

Applying our solution:

• Calculate ⌊√6⌋ = ⌊2.45⌋ = 2
• This correctly tells us that 2 bulbs remain on (the perfect squares 1 and 4 that are ≤ 6)

The key insight: Position 4 has divisors {1, 2, 4} - that's 3 divisors (odd), while position 6 has divisors {1, 2, 3, 6} - that's 4 divisors (even). Perfect squares like 4 have an odd number of divisors because one divisor (in this case, 2) pairs with itself.

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the sqrt() function performs a constant-time mathematical operation regardless of the input size n. Computing the square root is typically implemented using efficient algorithms like Newton's method or hardware-level instructions that complete in constant time.

The space complexity is O(1) because the algorithm only uses a fixed amount of additional memory to store the result of sqrt(n) and convert it to an integer, regardless of the input size. No additional data structures or recursive calls are used that would scale with the input.

Common Pitfalls

1. Floating-Point Precision Issues

The most critical pitfall in this solution is relying on floating-point arithmetic for the square root calculation. Due to floating-point representation limitations, math.sqrt(n) might produce results like 4.999999999999 instead of exactly 5.0 for perfect squares, leading to incorrect results when converting to integer.

Example of the problem:

# Potential issue with large perfect squares
n = 999999999999999999  # Very large number
# math.sqrt(n) might not be exact due to floating-point precision

Solution: Use integer-only arithmetic to avoid floating-point errors entirely:

class Solution:
    def bulbSwitch(self, n: int) -> int:
        # Integer-only solution using binary search
        if n == 0:
            return 0
      
        left, right = 1, n
        result = 1
      
        while left <= right:
            mid = (left + right) // 2
            if mid * mid <= n:
                result = mid
                left = mid + 1
            else:
                right = mid - 1
      
        return result

Alternative safer approach:

class Solution:
    def bulbSwitch(self, n: int) -> int:
        # Using isqrt from Python 3.8+ for exact integer square root
        import math
        if hasattr(math, 'isqrt'):  # Python 3.8+
            return math.isqrt(n)
        else:
            # Fallback with validation
            result = int(math.sqrt(n))
            # Verify and adjust if needed
            if (result + 1) ** 2 <= n:
                return result + 1
            return result

2. Forgetting Edge Cases

Not handling n = 0 properly. When there are no bulbs, the answer should be 0, but some implementations might not handle this gracefully.

Solution: Always add an explicit check:

def bulbSwitch(self, n: int) -> int:
    if n == 0:
        return 0
    return int(math.sqrt(n))

3. Misunderstanding the Problem

A common conceptual pitfall is attempting to simulate the actual toggling process, leading to an O(n²) solution that times out for large inputs:

# WRONG APPROACH - Don't do this!
def bulbSwitch(self, n: int) -> int:
    bulbs = [False] * (n + 1)  # This will TLE for large n
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            bulbs[j] = not bulbs[j]
    return sum(bulbs[1:])

Solution: Stick to the mathematical insight that only perfect squares remain on, avoiding simulation entirely.