Bulb Switcher

Medium Arrays & Hashing Math / Number Theory Original on LeetCode

Reported atLinkedIn

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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(n log n)Round r touches n / r bulbs, and n/1 + n/2 + ... + n/n is about n · ln n.
SpaceO(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.

  1. Create on[1..n], all false.
  2. For r = 1..n, for i = r, 2r, 3r, ... up to n: flip on[i].
  3. 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;
    }
}

2Optimal (count the perfect squares)

TimeO(1)One square root plus at most a couple of correction steps.
SpaceO(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.

  1. r = (int) sqrt(n).
  2. While r · r > n, decrease r; while (r + 1) · (r + 1) <= n, increase r (use 64-bit products).
  3. 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;
    }
}

Edge cases to test

  • 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

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.