**Reference:-** https://www.geeksforgeeks.org/puzzle-16-100-doors/

### Problem Statement

There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in following way:

In first walk, the person toggles every door

In second walk, the person toggles every second door, i.e., 2^{nd}, 4^{th}, 6^{th}, 8^{th}, â€¦

In third walk, the person toggles every third door, i.e. 3^{rd}, 6^{th}, 9^{th}, â€¦

â€¦â€¦â€¦

â€¦â€¦â€¦.

In 100^{th} walk, the person toggles 100^{th} door.

**Which doors are open in the end?**

### Solution:-

The solution lies in the fact that for each pair of divisors the door gets closed once again.So only those doors will be open whose no. of divisors will be odd.For example door 21 has factors ((1,21),(3,7)).So the door will be toggle 4 times and gets closed.

But there will be some doors whose no. of divisors would be odd.For example the 9 has factors (1,3,9) as 3*3=9 and the door will be toggled only once.

So the doors which will be opened are :-

1,4,9,16,25,36,49,64,81,100

### Implementation in Python:-

# -*- coding: utf-8 -*- """ Created on Thu Aug 22 00:37:58 2019 @author: Kapil Bansal """ def toggle(n): #This function changes the current position of door,if the door is open then it is closed otherwise it is opened if doors[n]==1: doors[n]=0 else: doors[n]=1 doors=[0]*100#Making a list and initializing them with 0 #Here 0 means that door is close and 1 means that door is open for i in range(1,101): j=i while j<=100: toggle(j-1) j=j+i for x in range(100):#printing the open doors. if doors[x]==1: print(x+1,end=" ")

### Output:-

### Efficient Approach

We can see from above that the doors which have odd no. of divisors are opened.Also only those doors will have odd no. of divisors that are perfect squares as each no. can be writtern in a product of two divisors.

For eg:-n=a*b But if n is a perfect square than a can be equal to b which will result only in a single divisor.

## 0 Comments