Domain 2MediumCORE

Bulb Switcher

We are given an integer n representing the number of bulbs, indexed from 1 to n. Initially, all bulbs are OFF. We perform a series of rounds where in round i, we toggle every bulb at index that is a multiple of i. After n rounds, we need to count how many remain ON.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Math#Brainteaser

319. Bulb Switcher

Model: qwen3.5:9b
Topics: Math,Brainteaser
FAANG asked: 1
Acceptance rate: 45.4%


Problem Breakdown

We are given an integer n representing the number of bulbs, indexed from 1 to n. Initially, all bulbs are OFF. We perform a series of rounds where in round i, we toggle every bulb at index that is a multiple of i. After n rounds, we need to count how many remain ON.

Key Inputs & Outputs:

  • Input: Integer n (0 <= n <= 10^9).
  • Output: An integer representing the final count of bulbs in the ‘ON’ state.

Constraints Analysis: The constraint N≤109N \le 10^9 is critical here. A simulation approach that iterates through rounds and toggles arrays would require roughly proportional to ∑i=1nn/i\sum_{i=1}^{n} n/i, which sums up to approximately O(nlog⁡n)O(n \log n) operations if optimized, or worse depending on implementation. More importantly, maintaining a state array of size 10910^9 is memory-prohibitive (though sparse representation might work). However, the time limit for LeetCode typically allows ≈108\approx 10^8 ops per second. An O(nlog⁡n)O(n \log n) approach will Time Out (TLE) on large inputs like 10910^9. We need a mathematical solution that is effectively constant time relative to n.

Intuition

Let’s trace the state of a specific bulb at index k (where 1≤k≤n1 \le k \le n).

  • Initially, it is OFF.
  • It gets toggled in round i if and only if k % i == 0. In other words, we toggle bulb k for every divisor of k.
  • The final state depends on the total number of times this bulb was toggled.
    • If it is toggled an even number of times: OFF →\to ON →\to OFF (ends OFF).
    • If it is toggled an odd number of times: OFF →\to ON →\to … →\to ON (ends ON).

So, a bulb ends up ON if and only if its index k has an odd number of divisors. In mathematics, the count of divisors for any integer is odd if and only if that integer is a perfect square. Non-square numbers have divisor pairs (a,b)(a, b) where a≠ba \neq b, resulting in even counts. Perfect squares have one unpaired factor (the root), making the total count odd.

Therefore, we simply need to count how many perfect squares exist between 1 and n inclusive (12,22,...,k21^2, 2^2, ..., k^2). This is equivalent to finding ⌊n⌋\lfloor \sqrt{n} \rfloor.

Approach

Since we established that the answer corresponds exactly to the number of perfect squares less than or equal to n, our algorithm simplifies significantly:

  1. Calculate the integer square root of n.
  2. Return this value directly as it represents kk where k2≤nk^2 \le n.

We do not need loops, arrays, or complex logic. We rely on a built-in mathematical function to compute n\sqrt{n}. In Python, we can use math.isqrt for integer precision safety (available in 3.8+) or cast the float result of exponentiation. Given N≤109N \le 10^9, standard floating-point precision is sufficient without loss of accuracy for this range.

Complexity Analysis

  • Time Complexity: O(1)O(1). Computing a square root using hardware instructions or optimized library functions takes constant time relative to input size (ignoring bit-depth considerations). Even if we consider the cost of arithmetic operations on large numbers, it is logarithmic with respect to n, which effectively behaves as constant for this problem scale.
  • Space Complexity: O(1)O(1). We use a fixed amount of memory regardless of n.

Solution

import math

class Solution:
    def bulbSwitch(self, n: int) -> int:
        """
        Returns the number of bulbs that are on after n rounds.
        
        Logic: A bulb at index k is toggled for every divisor of k. 
        It ends ON if it has an odd number of divisors (perfect square).
        We count perfect squares <= n, which equals floor(sqrt(n)).
        """
        # math.isqrt returns the integer part of the square root in Python 3.8+
        return math.isqrt(n)

# Fallback for older python versions if isqrt isn't available:
# import math
# def bulbSwitch(self, n): 
#     return int(math.sqrt(n))

Edge Cases Handled

  • n = 0: The square root of 0 is 0. Returns 0 correctly (no bulbs exist).
  • Small n (1, 2): Correctly identifies 12=11^2=1 as the only perfect square for inputs ≥1\ge 1.
  • Large n (10910^9): The mathematical approach avoids Time Limit Exceeded errors associated with simulation. Precision issues are avoided by using integer arithmetic or standard double precision which holds up to this magnitude without error affecting the floor result.