Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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:
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 <= 109Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
3
0
1
bulb-switcher-ii)minimum-number-of-k-consecutive-bit-flips)number-of-times-binary-string-is-prefix-aligned)find-the-pivot-integer)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #319: Bulb Switcher
class Solution {
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}
// Accepted solution for LeetCode #319: Bulb Switcher
func bulbSwitch(n int) int {
return int(math.Sqrt(float64(n)))
}
# Accepted solution for LeetCode #319: Bulb Switcher
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(sqrt(n))
// Accepted solution for LeetCode #319: Bulb Switcher
struct Solution;
impl Solution {
fn bulb_switch(n: i32) -> i32 {
(n as f64).sqrt() as i32
}
}
#[test]
fn test() {
let n = 3;
let res = 1;
assert_eq!(Solution::bulb_switch(n), res);
}
// Accepted solution for LeetCode #319: Bulb Switcher
function bulbSwitch(n: number): number {
return Math.floor(Math.sqrt(n));
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.