Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Lock unlock doors

------------------------------------------------------------------------------------

• There are 100 doors, all closed. A man does 100 passes infront of the doors.

In 1st pass, he opens all doors. In 2nd pass, he closes all doors multiples of 2.

In 3rd pass, he opens all doors multiples of 3 and so on.

In 100th pass, he closes door no 100 only.

After 100th pass, how many doors would be open?

------------------------------------------------------------------------------------

Doors are all closed initially.

So, if a door opens and does not close till the end, then it will remain open.

Also, if a door is opened, closed and re-opened (i.e. toggled 3 times), then it will be open.

So basically if a door is toggled an odd number of times, it will be open in the end.

All doors except 1st are toggled twice - once in the first pass and once in pass numbered after the door. Example: 5th door is toggled once initially and then in the 5th pass.

Also, doors are toggled in those passes when the pass is done for one of the factors making up that door number. Example: 6 will be toggled on 2nd and 3rd pass apart from 1st and 6th pass.

So, doors with an odd number of factors will remain open after the 100th pass.

Every number who has one factor, has another factor obtained by dividing the number by first factor. Only perfect squares are the numbers where this 2nd factor is same as the first factor.

So, only perfect squares and 1st door will have an odd number of toggles and so they will remain open after 100th pass.

Corollary: What if the man only makes N/2 passes i.e. in the above case, what if he makes only 50 passes and then stops?

In such a case, doors below 50 will follow the same logic as above.

Doors above 50 will be opened at least once (in the first pass). Then for every unique factor, then will be opened and closed once. Since all number between 50 and 100 have factors between 1 and 50, we can say that the passes which were to be made after 50 would have always involved toggling of a single door always. Example, pass 51 will toggle door 51 only, pass 87 would toggle door 87 only and so on.

This implies that if no passes are made after 50, every door above 50 will be in a state opposite to that if all 100 passes were made.

So, in this case, perfect square doors would be open below 50 and all doors except perfect squares will be open above 50!

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: