### 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(n^{2})

### 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

### Output:-

### 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=" ")

You must be logged in to post a comment.