Bulb Switcher Ii - Leetcode Solution

Problem Description:

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.

Example 1:

Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After first round, the three bulbs are [on, on, on]. After second round, the three bulbs are [on, off, on]. After 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

Solution:

The problem statement provides the following algorithm:

• Initially, all bulbs are off
• In the first round, we will turn on all bulbs.
• In the second round, we will toggle every second bulb (i.e., turn off if it is on and turn on if it is off).
• Similarly, in the ith round, we will toggle every i bulb.
• In the last round, we only toggle the last bulb.

We can solve this problem efficiently by using simple math.

Consider a bulb at position i. It is going to be toggled only if i is a factor of the round number. For example, let’s say i=6 and the round number is 3, then the bulb at position 6 is going to be toggled because 6 is a factor of 3. Similarly, bulb at 4 will be toggled in round 2 and it will be off after that.

So, all we need to do is to calculate the number of times a bulb will be toggled during n rounds and check whether it will be on or off at the end.

Let’s take a look at the sample input n=3. We have three bulbs, which will be toggled as follows:

• Bulb 1: round 1, round 3
• Bulb 2: round 1, round 2, round 3
• Bulb 3: round 1, round 3

If a bulb is toggled an even number of times (i.e., rounds), it will be off at the end, and if a bulb is toggled an odd number of times, it will be on at the end. Therefore, the solution is to count the number of bulbs that will be toggled an odd number of times.

Now, let’s take a look at the steps we will take to solve this problem.

Algorithm:

1. Initialize the count of bulbs that will be on to zero.
2. For each bulb i, calculate the number of times it will be toggled during n rounds by counting its factors.
3. If the number of times a bulb will be toggled is odd, increment the count of bulbs that will be on by 1.
4. Return the count of bulbs that will be on.

Code:

Here is the implementation of the above algorithm in Python:

def bulbSwitch(n: int) -> int: return int(n ** 0.5)

Test Cases:

We will use the following test cases to test the solution:

Test Case 1:

Input: n = 3 Expected Output: 1

Test Case 2:

Input: n = 0 Expected Output: 0

Test Case 3:

Input: n = 1 Expected Output: 1

Test Case 4:

Input: n = 99999 Expected Output: 316

The solution passed all test cases.

1