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.

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 switched an odd number of times.

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.

Divisors come in pairs, like i=12 has divisors 1 and 12, 2 and 6, and 3 and 4. Except when i is a square, like 36 has divisors 1 and 36, 2 and 18, 3 and 12, 4 and 9, and double divisor 6. So bulb i ends up on if and only if i is a square.

So just count the square numbers.

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

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)