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 is critical here. A simulation approach that iterates through rounds and toggles arrays would require roughly proportional to , which sums up to approximately operations if optimized, or worse depending on implementation. More importantly, maintaining a state array of size is memory-prohibitive (though sparse representation might work). However, the time limit for LeetCode typically allows ops per second. An approach will Time Out (TLE) on large inputs like . 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 ).
- Initially, it is OFF.
- It gets toggled in round
iif and only ifk % i == 0. In other words, we toggle bulbkfor every divisor ofk. - The final state depends on the total number of times this bulb was toggled.
- If it is toggled an even number of times: OFF ON OFF (ends OFF).
- If it is toggled an odd number of times: OFF ON … 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 where , 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 (). This is equivalent to finding .
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:
- Calculate the integer square root of
n. - Return this value directly as it represents where .
We do not need loops, arrays, or complex logic. We rely on a built-in mathematical function to compute . In Python, we can use math.isqrt for integer precision safety (available in 3.8+) or cast the float result of exponentiation. Given , standard floating-point precision is sufficient without loss of accuracy for this range.
Complexity Analysis
- Time Complexity: . 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: . 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 as the only perfect square for inputs . - Large
n(): 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.