Problem Statement:-
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 i<sup>th</sup> round, you toggle every i bulb. For the n<sup>th</sup> round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
Link: https://leetcode.com/problems/bulb-switcher/description/
Problem Explanation with examples:-
Example 1
COPY
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
Input: n = 0
Output: 0
Explanation: No bulbs are there.
Example 3
Input: n = 1
Output: 1
Explanation: Only one bulb is there so it will be on in the 1st iteration.
Constraints
0 <= n <= 10<sup>9</sup>
Intuition:-
We will use the fact that the number of times a bulb is toggled is equal to the number of factors of the number.
If the number of factors of a number is odd, then the bulb will be on and if the number of factors is even, then the bulb will be off.
Every prime number has 2 factors, 1 and the number itself. So, the bulb will be toggled 2 times so it will be off.
Every other number has even number of factors except for the perfect squares. So, the bulb will be toggled odd number of times and will be on.
So, we just need to find the number of perfect squares less than or equal to n and that is root(n).
Solution:-
- We will return the floor of the square root of n.
Code:-
JAVA Solution
class Solution {
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}
Python Solution
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(math.sqrt(n))
Complexity Analysis:-
TIME:-
The time complexity of the 1st code is O(1) as we are just doing constant time operations.
SPACE:-
The space complexity of both the code is O(1) as we are not using any extra space.