Bulb Switcher

Problem: 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:

Input: n = 2
Output: 1
Explanation: At first, the three bulbs are [off, off].
After the first round, the three bulbs are [on, on].
After the second round, the three bulbs are [on, off].
So we should return 1 because there is only one bulb is on.

Approach: Let's understand the problem first. All the bulbs are off at the beginning. After the first round, all the bulbs will be in on state(1,2,3,4,5,...n). After the second round, every second bulb will change its state which means state of bulbs at position 2,4,6,8,...(multiples of 2) will be changed. After the third round, state of every third bulb i.e. 3,6,9,12,...(multiples of 3) will be changed and so on.

Now if we see closely we will find out if odd numbers of operations are applied on a bulb then it will be in On state because starting state is off. for example Bulb one(1) will be always on because only one operation can be performed on this so we just have to find the number of operations performed on each bulb to decide it's state. if number of operations performed is odd then the bulb will be on and off otherwise. We can use the number of factors to know the number of operations as number of operations performed on bulb 'n' will be equal to number of factors of 'n'. Let's take an example to make it more clear:

Say n = 9. Let's see the factors of the numbers less than or equal to 9 -

• 1 - 1
• 2 - 1,2
• 3 - 1,3
• 4 - 1,2,4
• 5 - 1,5
• 6 - 1,2,3,6
• 7 - 1,7
• 8 - 1,2,4,8
• 9 - 1,3,9

Lets see when bulb 8 will be toggled:

• Round 1: Yes, every bulb is toggled
• Round 2: Yes, every 2nd bulb is toggled
• Round 3: No
• Round 4: Yes, every 4th bulb is toggled
• Round 5: No
• Round 6: No
• Round 7: No
• Round 8: Yes, every 8th bulb is toggled
• Round 9: No

Now if you see the number of times bulb 8 is toggled is equal to number of factors of 8 i.e. 4 (1, 2, 4 and 8). 

We know that factors always comes in pair for example 8 (1 and 8, 2 and 4) or 6 (1 and 6, 2 and 4) except numbers which are perfect square like 9(3 and 3 => only 3, 1 and 9) or 4 (1 and 4, 2 and 2 => only 2) so now we just have to check how many perfect square numbers are there which are less than or equal to our input number say 'n'. Now this is simple math, we can take the floor of the square root of 'n' to get this number. That's all. 

Implementation in C#:

        public static int BulbSwitch(int n)

        {

            return (int)Math.Sqrt(n);

        }

Complexity: O(1)