2 min read

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?

100-doors modified

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:
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
for i in range(2,n+1):
        while j<=n:
count=0#Counter to keep track of open doors
for i in range(n):
    if doors[i]==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
        if n%i==0 or n%(i+2)==0:
            return True
    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=" ")


Categories: Uncategorized

Kapil Bansal

A student of B.Tech CSE working on competitive programming, a cybersecurity devotee working towards strengthing the concepts. I am also working on Python modules, Data Structures and Algorithms etc.


Leave a Reply