Bulb Switcher
Bulb Switcher is a medium arrays & hashing problem solved with the math / number theory pattern.
The best approach, optimal (count the perfect squares), runs in O(1) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (simulate every round) up.
Problem
A hallway has n light bulbs numbered 1 to n, and all of them start off. You walk past them in n rounds. In round r (for r = 1, 2, ..., n) you flip the switch of every bulb whose number is a multiple of r: bulbs that were off turn on and bulbs that were on turn off.
So round 1 turns every bulb on, round 2 flips bulbs 2, 4, 6, ..., round 3 flips bulbs 3, 6, 9, ..., and the last round flips only bulb n.
Return how many bulbs are on after all n rounds.
Examples
Example 1
- Input
n = 5- Output
2- Why
- Only bulbs 1 and 4 have an odd number of divisors, so only they stay on after five rounds.
Example 2
- Input
n = 10- Output
3- Why
- The perfect squares 1, 4 and 9 are the bulbs left on.
Example 3
- Input
n = 0- Output
0- Why
- There are no bulbs at all.
Constraints
0 <= n <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (simulate every round) | O(n log n) | O(n) |
| Optimal (count the perfect squares) | O(1) | O(1) |
1Brute force (simulate every round)
O(n log n)Round r touches n / r bulbs, and n/1 + n/2 + ... + n/n is about n · ln n.O(n)One flag per bulb.Keep a boolean per bulb. In round r, flip every r-th bulb. At the end count the bulbs that are on.
- Create
on[1..n], all false. - For r = 1..n, for i = r, 2r, 3r, ... up to n: flip
on[i]. - Count the true entries.
class Solution {
public int bulbSwitch(int n) {
boolean[] on = new boolean[n + 1];
for (int r = 1; r <= n; r++) {
for (int i = r; i <= n; i += r) on[i] = !on[i];
}
int count = 0;
for (int i = 1; i <= n; i++) if (on[i]) count++;
return count;
}
}class Solution:
def bulbSwitch(self, n: int) -> int:
on = [False] * (n + 1)
for r in range(1, n + 1):
for i in range(r, n + 1, r):
on[i] = not on[i]
return sum(1 for i in range(1, n + 1) if on[i])class Solution {
public:
int bulbSwitch(int n) {
vector<bool> on(n + 1, false);
for (int r = 1; r <= n; r++) {
for (int i = r; i <= n; i += r) on[i] = !on[i];
}
int count = 0;
for (int i = 1; i <= n; i++) if (on[i]) count++;
return count;
}
};function bulbSwitch(n) {
const on = new Uint8Array(n + 1);
for (let r = 1; r <= n; r++) {
for (let i = r; i <= n; i += r) on[i] ^= 1;
}
let count = 0;
for (let i = 1; i <= n; i++) if (on[i]) count++;
return count;
}2Optimal (count the perfect squares)
O(1)One square root plus at most a couple of correction steps.O(1)Only a few integer variables.Bulb i is flipped once per divisor of i, and it is on at the end only if that count is odd. Divisors pair up as (d, i / d) except when d = i / d, which happens only for perfect squares. So the answer is the number of perfect squares in 1..n, which is floor(sqrt(n)). Take the floating-point root and nudge it by one in either direction so rounding can never give a wrong result.
- r = (int) sqrt(n).
- While r · r > n, decrease r; while (r + 1) · (r + 1) <= n, increase r (use 64-bit products).
- Return r.
class Solution {
public int bulbSwitch(int n) {
long r = (long) Math.sqrt(n);
while (r * r > n) r--;
while ((r + 1) * (r + 1) <= n) r++;
return (int) r;
}
}class Solution:
def bulbSwitch(self, n: int) -> int:
return math.isqrt(n)class Solution {
public:
int bulbSwitch(int n) {
long long r = (long long) sqrt((double) n);
while (r * r > n) r--;
while ((r + 1) * (r + 1) <= n) r++;
return (int) r;
}
};function bulbSwitch(n) {
let r = Math.floor(Math.sqrt(n));
while (r * r > n) r--;
while ((r + 1) * (r + 1) <= n) r++;
return r;
}Edge cases to test
n = 0(no bulbs)n = 1(the single bulb is switched on in round one and never touched again)nexactly a perfect square, or one less than a perfect square- The largest
n, where a simulation is far too slow and a floating-point square root must be checked
Hints
Hint 1
Bulb i is toggled once in round d for every divisor d of i. When does it end up on?
Hint 2
A bulb ends up on exactly when it is toggled an odd number of times, i.e. when it has an odd number of divisors.
Hint 3
Divisors come in pairs (d, i / d); the pair collapses into one only when i is a perfect square. Count the perfect squares up to n.
FAQ
What is the best time complexity for Bulb Switcher?
Optimal (count the perfect squares) runs in O(1) time and O(1) extra space. One square root plus at most a couple of correction steps.
Which pattern does Bulb Switcher use?
It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Reaching Points, Water and Jug Problem, Distribute Candies Among Children II.
Is there a brute force solution for Bulb Switcher?
Yes. Brute force (simulate every round) takes O(n log n) time and O(n) space. Keep a boolean per bulb.
Which edge cases should I test for Bulb Switcher?
n = 0 (no bulbs); n = 1 (the single bulb is switched on in round one and never touched again); n exactly a perfect square, or one less than a perfect square; The largest n, where a simulation is far too slow and a floating-point square root must be checked.