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.

OR

There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

Return the number of bulbs that are on after n rounds.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2

Input: n = 0
Output: 0

Example 3:

1
2

Input: n = 1
Output: 1

Solution

A bulb ends up on iff it is toggled an odd number of times.

You can figure out that for any given bulb, say bulb #42, you will toggle it for every divisor it has. so 42 has

  • 1 & 42
  • 2 & 21
  • 3 & 14
  • 6 & 7

So, in pass 1 i will switch on, pass 2 i will close it, pass 3 open, pass 6 close, pass 7 open, pass 14 close, pass 21 open, pass 42 close.

Call them bulb 1 to bulb n. Bulb i is switched in round d if and only if d divides i. So bulb i ends up on if and only if it has an odd number of divisors.

For every pair of divisors the bulb will just end up back in its initial state which is off. so you might think that every lock will end up off?

Well what about bulb #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only toggle bulb #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square locks will be open at the end.

So, how many perfect numbers are there from 1 to n?

So just count the square numbers upto n.

By using some examples we can find out the number of switches for each bulb:

1

For `9` - we have 1, 4, 9 - So, 3 bulbs will stay on.

And here is the detailed state:

1
2
3
4
5
6
7
8
9

1 -> 1 (1)
2 -> 2 (1 2)
3 -> 2 (1 3)
4 -> 3 (1 2 4)
5 -> 2 (1 5)
6 -> 4 (1 2 3 6)
7 -> 2 (1 7)
8 -> 4 (1 2 4 8)
9 -> 3 (1 3 9)

Method 1 – Naive Simulation (Count Divisors)

Intuition

For each bulb i (1 to n), count how many times it is toggled (i.e., how many divisors it has). If the number of divisors is odd, the bulb is on at the end. This is a brute-force approach and is slow for large n.

Approach

For each i from 1 to n:

  • Count the number of divisors of i.
  • If the count is odd, increment the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int bulbSwitch(int n) {
        int count = 0;
        for (int i = 1; i <= n; ++i) {
            int divisors = 0;
            for (int d = 1; d <= i; ++d) {
                if (i % d == 0) ++divisors;
            }
            if (divisors % 2 == 1) ++count;
        }
        return count;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func bulbSwitch(n int) int {
    count := 0
    for i := 1; i <= n; i++ {
        divisors := 0
        for d := 1; d <= i; d++ {
            if i%d == 0 {
                divisors++
            }
        }
        if divisors%2 == 1 {
            count++
        }
    }
    return count
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int bulbSwitch(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int divisors = 0;
            for (int d = 1; d <= i; d++) {
                if (i % d == 0) divisors++;
            }
            if (divisors % 2 == 1) count++;
        }
        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun bulbSwitch(n: Int): Int {
        var count = 0
        for (i in 1..n) {
            var divisors = 0
            for (d in 1..i) {
                if (i % d == 0) divisors++
            }
            if (divisors % 2 == 1) count++
        }
        return count
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def bulbSwitch(self, n: int) -> int:
        count = 0
        for i in range(1, n+1):
            divisors = 0
            for d in range(1, i+1):
                if i % d == 0:
                    divisors += 1
            if divisors % 2 == 1:
                count += 1
        return count
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn bulb_switch(n: i32) -> i32 {
        let mut count = 0;
        for i in 1..=n {
            let mut divisors = 0;
            for d in 1..=i {
                if i % d == 0 { divisors += 1; }
            }
            if divisors % 2 == 1 { count += 1; }
        }
        count
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    bulbSwitch(n: number): number {
        let count = 0;
        for (let i = 1; i <= n; i++) {
            let divisors = 0;
            for (let d = 1; d <= i; d++) {
                if (i % d === 0) divisors++;
            }
            if (divisors % 2 === 1) count++;
        }
        return count;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 – Math Insight (Count Perfect Squares)

Intuition

Each bulb is toggled once for every divisor it has. Divisors come in pairs, except for perfect squares (which have an odd number of divisors). Only bulbs at perfect square positions (1, 4, 9, …) are toggled an odd number of times and remain on. So, the answer is the number of perfect squares ≤ n.

Approach

Count all integers k such that k² ≤ n. This is simply floor(sqrt(n)).

Code

1
2
3
4
5
6

class Solution {
public:
    int bulbSwitch(int n) {
        return (int)sqrt(n);
    }
};
1
2
3
4

import "math"
func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n)))
}
1
2
3
4
5

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}
1
2
3
4
5
6

import kotlin.math.*
class Solution {
    fun bulbSwitch(n: Int): Int {
        return sqrt(n.toDouble()).toInt()
    }
}
1
2
3
4

import math
class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(math.sqrt(n))
1
2
3
4
5

impl Solution {
    pub fn bulb_switch(n: i32) -> i32 {
        (n as f64).sqrt() as i32
    }
}
1
2
3
4
5

class Solution {
    bulbSwitch(n: number): number {
        return Math.floor(Math.sqrt(n));
    }
}

Complexity

  • ⏰ Time complexity: O(1)
  • 🧺 Space complexity: O(1)