Lets Code Everyday

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 integer n 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 length n 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 array nums and an integer m as input, and it flips the switches of the bulbs that are multiples of m+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 the res 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 integer n 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 until i squared is greater than or equal to n. This condition is used because we only need to consider the bulbs up to the square root of n, 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 index i) 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 integer n 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.....😊