LeetCode 319: Bulb Switcher Solution in Python – A Step-by-Step Guide

What Is LeetCode 319: Bulb Switcher?

In LeetCode 319: Bulb Switcher, you’re given n bulbs, all initially off. You perform n rounds of toggling: in round k, you flip every kth bulb (1-based indexing). After all rounds, return the number of bulbs that are on. For example, with n = 3, the process leaves 1 bulb on. This problem tests your ability to spot patterns, connecting to mathematical concepts like factors and squares, with a nod to problems like LeetCode 204: Count Primes.

Problem Statement

• Input: An integer n (number of bulbs and rounds).
• Output: An integer—the number of bulbs on after n rounds.
• Rules:
• Bulbs start off (0).
• Round k toggles bulbs at indices k, 2k, 3k, ... (1-based).
• A bulb ends up on if toggled an odd number of times.

Constraints

• 0 <= n <= 10⁹

Examples

• Input: 3
• Output: 1 (Bulbs 1 and 4 on, 2 and 3 off)
• Input: 0
• Output: 0 (No bulbs)
• Input: 1
• Output: 1 (One bulb, toggled once)

Understanding the Problem: Counting Lit Bulbs

To solve LeetCode 319: Bulb Switcher in Python, we need to determine how many bulbs are on after n rounds of toggling. A naive simulation—flipping each bulb per round—is O(n²), impractical for n up to 10⁹. Instead, we’ll use:

• Best Solution (Mathematical): O(1) time, O(1) space—pure math magic.
• Alternative Solution (Simulation): O(n * √n) time, O(n) space—illustrative but slow.

Let’s start with the mathematical solution, explained in a beginner-friendly way.

Best Solution: Mathematical Insight (Square Numbers)

Why This Is the Best Solution

The mathematical approach is the top choice for LeetCode 319 because it’s blazing fast—O(1) time, O(1) space—and reveals a beautiful pattern: a bulb ends up on if and only if it’s a perfect square. This insight comes from counting toggles as factors, and it’s perfect for handling huge n values efficiently. It’s like cracking a code with math—no loops, just brilliance!

How It Works

Think of each bulb’s fate:

• Step 1: Toggle Counts:
• Bulb i is toggled when k divides i (e.g., bulb 6 toggled at 1, 2, 3, 6).
• Number of toggles = number of factors of i.
• Step 2: Odd or Even:
• Factors come in pairs (e.g., 6: (1,6), (2,3)), so toggles are usually even (off).
• Perfect squares have an odd number of factors (e.g., 4: 1, 2, 4), because one factor pairs with itself (2*2).
• Step 3: Count Squares:
• Bulbs on = count of squares ≤ n (e.g., n=5: 1, 4 → 2 bulbs).
• This is floor(sqrt(n)).
• Step 4: Why It Works:
• Only squares have odd toggles, turning them on.

It’s like spotting the square dancers in a crowd—simple once you see it!

Step-by-Step Example

Example: n = 4

• Bulb 1: Toggled at 1 (1 factor, on).
• Bulb 2: Toggled at 1, 2 (2 factors, off).
• Bulb 3: Toggled at 1, 3 (2 factors, off).
• Bulb 4: Toggled at 1, 2, 4 (3 factors, on).
• Squares: 1, 4 → 2 bulbs on.
• Result: floor(sqrt(4)) = 2

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def bulbSwitch(self, n: int) -> int:
        # Number of bulbs on = number of perfect squares <= n
        return int(n ** 0.5)

• Line 3: Compute square root of n and floor it.
• Time Complexity: O(1)—pure math operation.
• Space Complexity: O(1)—no extra space.

This is like a math-powered light switch—instant and elegant!

Alternative Solution: Simulation with Factor Counting

Why an Alternative Approach?

The simulation approach—O(n * √n) time, O(n) space—counts toggles explicitly for each bulb, offering a hands-on way to see the pattern. It’s slower and less practical for large n, but it’s great for learning how the process unfolds. It’s like flipping switches one by one to watch the magic happen!

How It Works

Simulate the toggling:

• Step 1: Initialize array for toggle counts.
• Step 2: For each round k:
• Increment count at multiples of k.
• Step 3: Count bulbs with odd toggles.

Step-by-Step Example

Example: n = 3

• Init: Counts = [0, 0, 0, 0]
• Round 1: Toggle 1, 2, 3 → [1, 1, 1]
• Round 2: Toggle 2 → [1, 2, 1]
• Round 3: Toggle 3 → [1, 2, 2]
• Result: Odd counts = [1] → 1 bulb on.

Code for Simulation Approach

Copy codeclass Solution:
    def bulbSwitch(self, n: int) -> int:
        if n == 0:
            return 0

        # Track toggle counts
        toggles = [0] * (n + 1)
        for k in range(1, n + 1):
            for i in range(k, n + 1, k):
                toggles[i] += 1

        # Count bulbs with odd toggles
        return sum(1 for t in toggles[1:] if t % 2 == 1)

• Time Complexity: O(n * √n)—harmonic series approximation of factor counting.
• Space Complexity: O(n)—toggle array.

It’s a switch-flipping simulator—illustrative but slow!

Comparing the Two Solutions

• Mathematical (Best):
• Pros: O(1) time, O(1) space, perfect for large n.
• Cons: Requires math insight.
• Simulation (Alternative):
• Pros: O(n * √n) time, O(n) space, shows process.
• Cons: Impractical for n = 10⁹.

Math wins hands down.

Additional Examples and Edge Cases

• n = 5: 2 (1, 4).
• n = 10: 3 (1, 4, 9).
• n = 0: 0.

Both handle these correctly.

Complexity Breakdown

• Mathematical: Time O(1), Space O(1).
• Simulation: Time O(n * √n), Space O(n).

Math is the clear victor.

Key Takeaways

• Mathematical: Squares light the way—genius!
• Simulation: Toggle and see—educational!
• Python: Math ops shine—see [Python Basics](/python/basics).
• Logic: Patterns beat brute force.

Final Thoughts: Illuminate the Solution

LeetCode 319: Bulb Switcher in Python is a mathematical delight disguised as a coding challenge. The square-root solution offers speed and elegance, while simulation provides a tangible process. Want more math-based puzzles? Try LeetCode 204: Count Primes or LeetCode 279: Perfect Squares. Ready to count bulbs? Head to Solve LeetCode 319 on LeetCode and light up that answer today!