## Question

There are D doors in a long hallway. They are all closed. The first time you walk by each door, you open it. The second time around, you clos-e every second door (since they are all opened). On the third pass you stop at every third door and open it if it’s closed, close it if it’s open. On the fourth pass, you take action on every fourth door. You repeat this pattern for I passes. D and I may or may not be equal. At the end of I passes, what doors are opened and what doors are closed?

## Solution:

As with my general approach to programming, I am taking an iterative approach to the solution. We take a trivial approach first, an optimal solution with I == D and finally, an optimal solution with I <> D.

### Trivial Solution:

An array of boolean values is initialized with `false` (implies closed) representing the state of the doors. It involves two loops. The outer one is for each pass and the inner loop is for the doors. The value in the element is toggled based on the two iterations.

#### Complexity

Since we have two loops both parsing through the complete length of the array, this solution for the problem has a time complexity of O(n

^{2}). However, the memory complexity is O(n) only.### Optimal Solution with I == D:

We use a single loop and determine if a number is a square or not. If the number is a perfect square of some other number, then it will be open. All other doors will be closed.

#### Explanation:

Consider the doors numbered from 1 to 10:

- This door is toggled once only - when the first pass is done. Hence, the state will be `true` at the end.
- This door is toggled two times - once during the first pass. Hence, the state will be `false` at the end.
- This door is toggled two times - once during the first pass. Hence, the state will be `false` at the end.
- This door is toggled three times - once during the first, second and fourth passes. Hence, the state will be `true` at the end.

- This door is toggled two times - once during the first and fifth passes. Hence, the state will be `false` at the end.

- This door is toggled four times - once during the first, second, third and sixth passes. Hence, the state will be `false` at the end.

- This door is toggled two times - once during the first and seventh passes. Hence, the state will be `false` at the end.

- This door is toggled four times - once during the first, second, fourth and eighth passes. Hence, the state will be `false` at the end.

- This door is toggled three times - once during the first, third and ninth passes. Hence, the state will be `true` at the end.

- This door is toggled four times - once during the first, second, fifth and tenth passes. Hence, the state will be `false` at the end.

As you can see, except for perfect squares, the other numbers have an even number of factors. When there are even number of factors, the door gets closed again.

#### Complexity

The optimal solution has a time complexity of O(n) and memory complexity of O(n).

### Optimal Solution with I <> D

One of my friends found a problem with this logic. The discussion is documented here. I will be fixing the bug and updating this post at the earliest.

Now, let us consider another layer of complication on top of this. What would happen if the number of iterations is not equal to the number of doors in the room?

First off, we only need to consider the case where I > D, since there is no door whose state will be toggled because of the iterations.

For other cases, the logic of squares being closed and others being open would not be completely true any more. The last toggle of the doors where D > I would never happen. Now, the influencers are whether the door number is a perfect square and whether current door number < I. The following table gives the truth table after considering this scenario:

Is (door + 1) a perfect square? | Is (door + 1) less than or equal to Number of iterations | Is Door Closed? |
---|---|---|

true | true | true |

false | true | false |

true | false | false |

false | false | true |

As can be seen, this follows XNOR logic.

#### Complexity

This solution has a time complexity of O(n) and memory capacity of O(n).