You need to find the state of the 'k'th switch/bulb (1
Expected O(1) time and space complexity.
 
|
|
 
|
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.
You need to find the state of the 'k'th switch/bulb (1
Expected O(1) time and space complexity.
Subscribe to:
Post Comments (Atom)
2 comments:
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.
Madan
@Madan
As far as I understand, your soln holds correct only for the cases where i >= k.
The soln I could think of is to find all the factors of k that are less than or equal to i and if their count is odd, then its ON otherwise its OFF.
Post a Comment