N Doors Puzzle

There are N doors in a row, numbered from 1 to N. Initially all are closed. Then you make N passes by N doors. In first pass you toggle (open the door if it is closed and close it if it is opened) all the doors starting from the first door. In the second pass you toggle every door whose number is a multiple of 2 (2, 4, 6, 8, 10…). In 3rd pass you toggle doors whose number is multiple of 3 (3, 6, 9, ..) and so on.. In the i‘th pass you toggle all the doors which are multiple of i. What will be the state of k‘th door after all the passes?

Solution:

This is a classic interview question. The idea is that for any door say No. 18, the door will be toggled at the pass which is a factor of 18.

(1, 2, 3, 6, 9, 18). Now the question reduces to how many factors are there in a number.

Generally all the numbers have even number of factors because the factors pair up. For example: In case of 18, the pairs are

• 1 – 18
• 2 – 9
• 3 – 6

So the door will be ultimately closed for such numbers where the factors of the number are even.

The door will only be open for the numbers which has odd number of factors. What are these numbers?

Are they the prime numbers? No! because any prime numbers, p, will have factor 1 & p itself, hence even.

Only the perfect squares are the numbers which has odd number of factors. For example:

9

will have factors 1, 3, 9

16

will have factors 1, 2, 4, 8, 16

and so on.

Hence, the k‘th door will be open if k is a perfect square, otherwise it will be closed.