100 Doors Interview Puzzle || Microsoft Interview Puzzle

There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggles (which means if the door is open then close if door is closed then open) person does this in the following way:

In the first walk, the person toggles every door that is 1, 2,3, 4, till the 100th door. In the second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, and so on till the 100th door. In the third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, 12th so on till 99 in other words person toggles all doors which are  multiple of 3

In the 100th walk, the person toggles the 100th door. Which doors are open in the end?

Solution:

according to the problem statement, In the first walk, the person toggles every door that is 1, 2,3, 4, till the 100th door

hence after the first walk, every door is open. 

In the second walk, the person toggles every second door, i.e., 2^nd, 4^th, 6^th, 8^th, and so on till the 100th door

hence on the second walk person only visit the even doors so at the end of the second walk the even doors are closed and the odd ones are opened. 

In the third walk, the person toggles every third door, i.e. 3^rd, 6^th, 9^th, 12th so on till the 99th door. in the third time person will close door 3 (opened from the first pass), open door 6 (closed from the second pass), and person will close door 9 (opened from the first pass), open door 12 (closed from the second pass), and it repeats...

A door is toggled in an n^th walk if n divides door number. 

For example, door number 45 is toggled in 1^st, 3^rd, 5^th, 9^th, 15^th, and 45th walk because these are the numbers that divide 45.

The door is switched back to the initial stage for every pair of divisors. For example, 45 is toggled 6 times for 3 pairs (1, 45), (3, 15), and (5, 9).

so on pass 1 person will open the door, pass 3 he will close it, pass 5 he will open it, pass 9 he will close it, pass 15 he will open it, pass 45 he will close it.  for every pair of divisors, the door will just end up back in its initial state.

let's consider one more example

say door #42, a person will visit it for every divisor it has. so 42 has 1 & 42, 2 & 21, 3 & 14, 6 & 7. so on pass 1 person will open the door, pass 2 he will close it, pass 3 he will open it, pass 6 he will close it, pass 7 he will open it, pass 14 he will close it, pass 21 he will open it, pass 42 he will close it. for every pair of divisors, the door will just end up back in its initial state.

It looks like all doors would become closed at the end. 

But there are door numbers which would become open, example door #9. 9 has the divisors 1 & 9, 3 & 3. but 3 is repeated because 9 is a perfect square, so you will only visit door #9, on pass 1, 3, and 9… leaving it open at the end. only perfect square doors will be open at the end.

So the answer is all perfect squares that are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.