2 min read

Reference:- https://freshlybuilt.com/100-doors-problem-using-python/

Problem Statement

This is a general form of 100 doors problem.Here you have n doors.All doors are initially closed.m persons walk through all the doors and toggle them(open if close and vice-versa).

Person 1 walks and toggle(open) all doors.

Person 2 walks and toggle each door that is a multiple of 2,i.e.,2nd,4th,6th,8th,…

Person 3 walks and toggle each door that is a multiple of 3,i.e.,3rd,6th,9th,12th,…

………………………..

…………………………

Person m walks and toggle each door that is multiple of m.

Which doors are open in the end?

Solution:-

The solution is somewhat similar to the 100 doors problem.Each door that has odd no. of walks will be opened and rests will be closed.Now if there are m walks then all door no. which are less than m and a perfect square will be opened.But for other doors ,i.e., where door no. is greater than n the scenario will change and some more doors will be added to the list.

For Example:-

Let there are 5 doors and 3 persons.

Then Person 1 will open each door.

Person 2 will close doors that are even,i.e. door 2 and door 4.

Person 3 will close door 3.

In this case,the answer is 1 and 5.

Implementation in Python:-

#Here 0 represents that door is close and 1 represents that door is open.
def toggle(n):
#closes door if they are open and opens if they are closed.
    if doors[n]==1:
        doors[n]=0
    else:
        doors[n]=1
n=int(input('Enter the no. of doors available'))
m=int(input('Enter the no. of persons'))
doors=[0]*n#Initializing n doors with 0.(They are closed initially)
for i in range(1,m+1):#Iterating through m times
    j=i
    while j<=n:
        toggle(j-1)
        j=j+i
for x in range(n):
    if doors[x]==1:
        print(x+1,end=" ")

Output:-

n-doors

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.

0 Comments

Leave a Reply