100 doors problem(Modified) using Python2 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 second walk he opens each door that is a multiple of two but close door 2 later.

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

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

Similarly in i-th walk he opens each door that is a multiple of i and close i-th door later.

Which doors are open at end?

100-doors
100-doors modified

Naive Approach

The basic approach would be to to start from 2 and go till 100 and keep the track of which doors 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

Output:-

100-doors
modified-100doors

Efficient Approach

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

Output:-

Bookmark(0)
Tags:

Add a Comment

Your email address will not be published. Required fields are marked *