# 100 doors problem(Modified) using Python

### Problem Statement:-

There are 100 doors and a person walks through it in such a way that:-

In first walk he opens first door

In the second walk, he opens each door that is a multiple of two except door 2.

……………………………………

…………………………………..

Similarly, in i-th walk, he opens each door that is a multiple of i except i-th door.

Which doors are open at end?

### Naive Approach

The basic approach would be to to start from 2 and go till 100 and keep the track of doors which are opened and which are closed. Then print the no. of open doors. But its time complexity will be:-O(n2)

### Code in Python

```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]==0:
doors[n]=1
n=100 #No. of doors(Can be changed for a general n-doors problem.)
doors=[0]*n #Making a list and initializing them with 0
#Here 0 means that door is close and 1 means that door is open
doors[0]=1
for i in range(2,n+1):
j=i+i
while j<=n:
toggle(j-1)
j=j+i
count=0#Counter to keep track of open doors
for i in range(n):
if doors[i]==1:
count=count+1
print(i+1,end=" ")#Printing the open doors
print() #Inserting a new line after printing all doors that are open
print("\n No. of open doors are",count)#Total no. of open doors```

### Efficient Approach

From the above output, it can be observed that only those doors are opened that are not prime. So, we can directly print all those numbers that are not prime rather than keeping track of which doors are opened or not.

```def not_prime(n):
if n==1:
return True
if n<=3:
return False
if n%2==0 or n%3==0:#Used so that we can skip 5 numbers in each iteration
return True
i=5
while(i*i<=n):
if n%i==0 or n%(i+2)==0:
return True
i=i+6
return False
n=100#It can be changed with the number of doors
print(*[str(i)+" " if not_prime(i) else '' for i in range(1,n+1)],end=" ")```

Tags: