Problem Explanation:

Given 'n' bulbs, the problem is to determine the number of bulbs that will be turned on after 'n' rounds.

Starting with all the bulbs turned off, you perform the following operations:

1. In the first round, all the bulbs are turned on.
2. In the second round, every second bulb is turned off.
3. In the third round, the state of every third bulb is toggled.
4. This pattern continues until the 'n-th' round - where only the 'n-th' bulb is toggled.

The task is to return the number of bulbs that will be left turned on after 'n' rounds.

Approach

The interesting pattern here is that a bulb is toggled each time one of its divisors is processed. So the bulb will end up being 'on' only if it has an odd number of divisors.

After observing closely we could see that only perfect square numbers have odd number of divisors. For example, factors of 4 (perfect square) are 1, 2 and 4. Factors of 36 (another perfect square) are 1, 2, 3, 4, 6, 9, 18 and 36.

So, all we need to do is count all the perfect squares less than or equal to 'n' by calculating the square root of 'n'.

Example

For example, if we are given 'n' as 10, the perfect square numbers less than 'n' are 1, 4 and 9. The count of perfect squares is 3. So, 3 bulbs will be left on after 10 rounds.

Python Solution

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

Java Solution

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

JavaScript Solution

1
2javascript
3var bulbSwitch = function(n) {
4    return Math.floor(Math.sqrt(n));
5};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int bulbSwitch(int n) {
6        return sqrt(n);
7    }
8};

C# Solution

1
2csharp
3public class Solution {
4    public int BulbSwitch(int n) {
5        return (int)Math.Sqrt(n);
6    }
7}

Each solution effectively uses a sqrt function (provided by the respective languages' built-in libraries) to calculate the square root of a given 'n', which returns the number of perfect squares less than or equal to 'n'. The int or floor function is used to eliminate any decimal point numbers. This gives the number of bulbs that will remain turned on after 'n' rounds.# R Solution

R, though not a strictly used programming language for competitive coding, also provides an easy way to solve this problem, similar to the other programming languages.

1
2R
3bulbSwitch <- function(n) {
4  return(as.integer(sqrt(n)))
5}

This solution uses the sqrt() function to calculate the square root of 'n' and the as.integer() function to convert the result to an integer. As R inherently does not discard the decimal portion of numbers after performing mathematical operations, converting the result to an integer is necessary.

Conclusion

Understanding the problem and observing patterns is the key to solving this problem efficiently. By understanding that perfect squares are the only numbers with an odd number of divisors, we can derive that these are the only bulbs that will remain 'on' after 'n' rounds. This allows us to write a very efficient solution with O(1) time complexity, i.e., the running time of the program in any of the above mentioned languages will be more or less constant, irrespective of the size of 'n'.

Likewise, the space complexity of this solution is also O(1), which means that the amount of memory used does not change with the size of the input integer, making it an extremely efficient solution.