# 100 Switches & 100 bulbs

There are 100 switches in a room operating 100 bulbs. At iteration '0' all switches are OFF. For every iteration 'i', all switches that are multiples of 'i' are toggled (turn OFF if ON, turn ON if OFF).

You need to find the state of the 'k'th switch/bulb (1<=100) after the 'i' th iteration

Expected O(1) time and space complexity.

Lets calculate what the state of the bulb i will be with few examples.

If i = 6, the ith bulb will be toggled for 1,2,3,6 multiples. So it will be back to the state where it started as there are even number of toggles.

If i = 25, then 1,5,25 are the only factors of i. So the state of the ith bulb will be the opposite of what you started from.

Look at what caused the difference in both the cases.

In the first case,
1*6 = 2*3 = 6
In the 2nd case,
1*25, 5*5 = 25

In the 2nd case, we have same factor multiplied twice. ie if the factor is f, then the given number has been f^2 which reduced the toggle by 1.

So the answer is, all the square numbers within 100 will be in one state and the rest of the numbers will be in the other state.