Bulb Switcher solution and explanation
Infosys
Google
TCS
9 more videos on this problem
LeetCode 319. Bulb Switcher - Math Trick Fully Explained [Coding Interview Question]Shiran Afergan · 7:20 · 10K views
Bulb Switcher || Programming Maths || Leetcode 319Aryan Mittal · 13:05 · 8K views
Bulb Switcher | With Intuition | AMAZON | Leetcode 319 | codestorywithMIKcodestorywithMIK · 12:07 · 6K views
Bulb Switcher - Leetcode 319 - PythonTechError · 5:39 · 1K views
319. Bulb Switcher | LEETCODE MEDIUM | MATHcode Explainer · 10:14 · 1K views
Bulb Switcher| LeetCode| Data Structure| Algorithms| Coding| InterviewsLearning Dev · 4:26 · 1K views
Daily Leetcode #1122: Apr 27, 2023 - 319. Bulb SwitcherProgramming Live with Larry · 10:25 · 640 views
Bulb Switcher Leetcode Explained | Math Pattern Behind hte LogicByteQuest · 2:32 · 617 views
319. Bulb Switcher | Leetcode | Math | FundamentalsCoding with Tamilarasan · 5:25 · 395 views
L-14 | Bulb Switcher - LeetCode 319 | DSA Series #dsa #leetcode #codingThe Code Planet · 15:47 · 330 views
The problem
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 <= 109
Approach overview
Problem Overview: You have n bulbs initially turned off. On round 1 every bulb is toggled, on round 2 every second bulb is toggled, on round 3 every third bulb, and so on until round n. The task is to determine how many bulbs remain on after all rounds finish.
Approach 1: Counting Perfect Squares by Iteration (O(√n) time, O(1) space)
The key observation is that a bulb toggles once for every divisor of its index. For example, bulb 12 toggles on rounds 1, 2, 3, 4, 6, and 12. Most numbers have divisors in pairs such as (2,6) or (3,4), which results in an even number of toggles and the bulb ends up off. Only perfect squares have an odd number of divisors because one divisor pair collapses (e.g., 3 × 3). That means bulbs at positions 1, 4, 9, 16... stay on. Iterate i while i * i ≤ n and count how many perfect squares exist.
This approach directly models the mathematical insight without relying on built-in square root functions. It works well when you want explicit control over iteration or when implementing the logic in constrained environments. The algorithm performs about √n iterations and uses constant memory.
Approach 2: Perfect Square Insight (O(1) time, O(1) space)
The observation above leads to a simpler solution: the number of bulbs that remain on equals the number of perfect squares less than or equal to n. That value is simply ⌊√n⌋. Instead of simulating toggles, compute the integer square root of n and return it.
This converts a simulation problem into a pure math calculation. The toggle pattern becomes irrelevant once you recognize the divisor parity property of numbers. Because the algorithm performs only a single square root operation, the runtime is effectively constant with O(1) space. This is the intended optimal solution and a classic brainteaser style problem frequently seen in interviews that test pattern recognition rather than brute-force simulation.
Recommended for interviews: Interviewers expect the perfect square observation. Mentioning that bulbs toggle once per divisor demonstrates understanding of the mechanics, while deriving the ⌊√n⌋ formula shows strong problem-solving ability. Starting with the divisor reasoning and then simplifying to the math solution communicates both intuition and optimization.
Approach 1: Perfect Square Insight
In this approach, we observe that bulbs that remain on are those that are toggled an odd number of times. Typically, a bulb indexed at i is toggled once for every divisor it has. Numbers which are perfect squares have an odd number of divisors (since one of its divisors is repeated, for example, the square root). Hence, the number of bulbs that will remain on is determined by the number of perfect squares up to n. Therefore, the number of bulbs left on is the integer part of the square root of n.
import math
def bulbSwitch(n: int) -> int:
return int(math.sqrt(n))class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}#include <cmath>
int bulbSwitch(int n) {
return static_cast<int>(sqrt(n));
}function bulbSwitch(n) {
return Math.floor(Math.sqrt(n));
}#include <math.h>
int bulbSwitch(int n) {
return (int)sqrt(n);
}using System;
public class Solution {
public int BulbSwitch(int n) {
return (int)Math.Sqrt(n);
}
}This solution leverages the math.sqrt function to get the square root of n and then converts it to an integer, providing the count of perfect square numbers up to n.
Time Complexity: O(1) since math square root is a constant operation.
Space Complexity: O(1), with no additional space complexity.
Approach 2: Counting Perfect Squares by Iteration
This approach involves explicitly counting all perfect squares up to n by probing through potential perfect squares. Starting from 1, we continue as long as i*i is less than or equal to n, incrementing the counter each time. This direct enumeration is straightforward and still only traverses a limited range due to the root domain.
def bulbSwitch(n):
count = 0
i = 1
while i * i <= n:
count += 1
i += 1
return countclass Solution {
public int bulbSwitch(int n) {
int count = 0;
for (int i = 1; i * i <= n; i++) {
count++;
}
return count;
}
}int bulbSwitch(int n) {
int count = 0;
for (int i = 1; i * i <= n; i++) {
count++;
}
return count;
}function bulbSwitch(n) {
let count = 0;
for (let i = 1; i * i <= n; i++) {
count++;
}
return count;
}int bulbSwitch(int n) {
int count = 0;
for (int i = 1; i * i <= n; i++) {
count++;
}
return count;
}public class Solution {
public int BulbSwitch(int n) {
int count = 0;
for (int i = 1; i * i <= n; i++) {
count++;
}
return count;
}
}This Python method employs a while loop to explore the number of i values satisfying i * i ≤ n, effectively counting perfect squares below n.
Time Complexity: O(√n) since it evaluates each integer i up to √n.
Space Complexity: O(1) highlights absence of extra space use.
Approach 3: Mathematics
We can number the n bulbs as 1, 2, 3, cdots, n. For the i-th bulb, it will be operated in the d-th round if and only if d is a factor of i.
For a number i, the number of its factors is finite. If the number of factors is odd, the final state is on; otherwise, it is off.
Therefore, we only need to find the number of numbers from 1 to n with an odd number of factors.
For a number i, if it has a factor d, then it must have a factor i/d. Therefore, numbers with an odd number of factors must be perfect squares.
For example, the factors of the number 12 are 1, 2, 3, 4, 6, 12, and the number of factors is 6, which is even. For the perfect square number 16, the factors are 1, 2, 4, 8, 16, and the number of factors is 5, which is odd.
Therefore, we only need to find how many perfect squares there are from 1 to n, which is \lfloor \sqrt{n} \rfloor.
The time complexity is O(1), and the space complexity is O(1).
function bulbSwitch(n: number): number {
return Math.floor(Math.sqrt(n));
}func bulbSwitch(n int) int {
return int(math.Sqrt(float64(n)))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Perfect Square Insight | Time Complexity: O(1) since math square root is a constant operation. |
| Counting Perfect Squares by Iteration | Time Complexity: O(√n) since it evaluates each integer i up to √n. |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Perfect Squares by Iteration | O(√n) | O(1) | When you want to explicitly count perfect squares without using built-in sqrt functions |
| Perfect Square Insight (Math) | O(1) | O(1) | Optimal interview solution using the observation that only perfect square indices remain on |
Frequently asked questions
Is Bulb Switcher easy or hard?
Bulb Switcher is labeled Medium on LeetCode because the brute-force simulation is straightforward but inefficient. The challenge is identifying the mathematical pattern that only perfect square positions remain on.
Bulb Switcher Python/Java solution
In both Python and Java, compute the integer square root of n and return it. Python typically uses int(math.sqrt(n)), while Java uses (int)Math.sqrt(n). Both implementations run in constant time and require no additional memory.
How to solve Bulb Switcher in O(1)?
Recognize that bulbs toggle once for each divisor of their position. Only perfect squares have an odd number of divisors, meaning they end in the ON state. Count how many perfect squares are ≤ n, which is floor(sqrt(n)).
What is the best approach for Bulb Switcher?
The optimal approach uses the perfect square insight. A bulb toggles once for every divisor of its index, and only perfect squares have an odd number of divisors. Therefore the number of bulbs that remain on equals floor(sqrt(n)). This runs in O(1) time with O(1) space.
Is Bulb Switcher asked at Google/Amazon/Meta?
Bulb Switcher is a classic math and reasoning interview problem that has appeared in variations at companies like Google, Amazon, and Meta. It tests pattern recognition and the ability to reduce a simulation problem to a mathematical insight.
What data structure is used in Bulb Switcher?
No special data structure is required for the optimal solution. The problem reduces to a mathematical observation about divisors and perfect squares, so the implementation only needs a square root calculation and basic arithmetic.
What is the time complexity of Bulb Switcher?
The optimal math solution runs in O(1) time because it simply computes the integer square root of n. An alternative iterative method counts perfect squares up to n, which takes O(√n) time and O(1) space.