Question - 24:
Bulb Switcher
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.
Example 1:
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
Example 3:
Input: n = 1
Output: 1
First approach:
class Solution {
public int bulbSwitch(int n) {
if(n==0) return 0;
else if(n==1) return 1;
int[] arr= new int[n];
int res=0;
for(int i=0;i<n;i++) arr[i]=1;
for(int i=1;i<n;i++) toggle(arr,i);
for(int i:arr) if(i==1) res++;
return res;
}
public static void toggle(int[] nums,int m){
int x=m+1;
for(int i=m;i<nums.length;i=i+x)
{
if(nums[i]==0) nums[i]=1;
else nums[i]=0;
}
}
}
Step-by-step implementation:
The
bulbSwitch
method takes an integern
as input and returns an integer value. It first checks if n is 0 or 1, and if so, it returns the respective value. Otherwise, it proceeds with the implementation.An integer array
arr
of lengthn
is created to store the status of the bulbs. Initially, all bulbs are turned off, so the array is initialized with the value 1 for each element.An integer variable
res
is initialized to 0 to count the number of bulbs that are on.The first for loop initializes all bulbs to be turned on by setting the value of each element in the
arr
array to 1.The second for loop iterates from 1 to n-1, and in each iteration, it calls the
toggle
method to flip the switches of the bulbs that are multiples of the current iteration number.The
toggle
method takes an integer arraynums
and an integerm
as input, and it flips the switches of the bulbs that are multiples ofm+1
. In each iteration, it checks if the current bulb is turned off, and if so, it turns it on by setting its value to 1. Otherwise, it turns it off by setting its value to 0.The third for loop iterates over the
arr
array and counts the number of bulbs that are turned on. It increments theres
variable for each bulb that is turned on.The
res
variable is returned as the output of the method, which represents the number of bulbs that are turned on.
The time complexity of the given code is O(n*sqrt(n)).
The for loop that calls the toggle
method runs n-1 times, and the toggle
method itself has a time complexity of O(n/m) where m is the iteration number. Therefore, the total time complexity can be calculated as follows:
1 + (2 + 3 + 4 + ... + n-1) = 1 + (n-2)*(n-1)/2 = O(n^2)
Inside the toggle
method, the for loop runs n/m times, and each iteration involves a constant number of operations. Therefore, the time complexity of the toggle
method is O(n/m).
Therefore, the overall time complexity of the bulbSwitch
method is O(n^2/n + n^2/(n-1) + ... + n^2/2), which can be simplified to O(n*sqrt(n)) using the harmonic series approximation.
The space complexity of the code is O(n), as it creates an array of size n to store the status of the bulbs. The other variables used in the code have a constant space complexity, so they do not affect the overall space complexity.
Second approach:
class Solution {
public int bulbSwitch(int n) {
int num = 0;
for(int i = 1; i*i <=n ; i ++){
num++;
}
return num;
}
}
Step-by-step implementation:
The
bulbSwitch
method takes an integern
as input and returns an integer value.An integer variable
num
is initialized to 0 to count the number of bulbs that will be turned on in the end.The for loop starts with
i
equal to 1 and continues untili
squared is greater than or equal ton
. This condition is used because we only need to consider the bulbs up to the square root ofn
, as all the other bulbs would have been toggled multiple times by then.In each iteration of the for loop, the
num
variable is incremented by 1, as the current bulb (with indexi
) will be toggled on.After the for loop, the
num
variable represents the number of bulbs that will be turned on in the end.The method returns the
num
variable as the output.
The time complexity of the given code is O(sqrt(n)).
The for loop runs for all values of i
from 1 to the square root of n
. Since there are only O(sqrt(n)) such values, the time complexity of the loop is O(sqrt(n)).
The space complexity of the code is O(1). The code only uses a constant amount of space to store the num
variable, the loop variable i
, and some other internal variables. Therefore, the space complexity is constant and does not depend on the input size n
.
Third approach:
class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}
Step-by-step implementation:
The
bulbSwitch
method takes an integern
as input and returns an integer value.The method simply calculates the square root of
n
using the Math.sqrt() method and casts the result to an integer using the(int)
typecast operator.The result of the method is the integer value representing the number of bulbs that will be turned on in the end.
The implementation of the code is based on the observation that only the perfect square numbered bulbs remain on in the end. Therefore, the code calculates the square root of n
and returns the integer part of the square root, which represents the number of bulbs that will be turned on.
This implementation is more efficient than the previous implementation as it doesn't require iterating through each bulb and checking whether it is turned on or off. Instead, it directly calculates the answer using the mathematical property of perfect squares.
The time complexity of this implementation is O(1), as it performs a single mathematical operation regardless of the input value n
.
The space complexity of the code is O(1), as it only uses a constant amount of space to store the integer result of the method.
Thanks for reading...Happy coding.....😊