100 doors problem Using Python

100 doors problem Using Python

2 min read

Reference:- https://www.geeksforgeeks.org/puzzle-16-100-doors/

Problem Statement

There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in following way:

In first walk, the person toggles every door

In the second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, and so on.

In third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, and so on.

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

In 100th walk, the person toggles 100th door.

Which doors are open in the end?

Can you solve it?

Solution:-

The solution lies in the fact that for each pair of divisors the door gets closed once again. So only those doors will be open whose no. of divisors will be odd.For example door 21 has factors ((1,21),(3,7)).So the door will be toggle 4 times and gets closed.
But there will be some doors whose no. of divisors would be odd. For example, the 9 has factors (1,3,9) as 3*3=9 and the door will be toggled only once.

So the doors which will be opened are :-
1,4,9,16,25,36,49,64,81,100

Implementation in Python:-

# -*- coding: utf-8 -*-
"""
Created on Thu Aug 22 00:37:58 2019

@author: Kapil Bansal
"""
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]==1:
        doors[n]=0
    else:
        doors[n]=1
doors=[0]*100#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(1,101):
    j=i
    while j<=100:
        toggle(j-1)
        j=j+i
for x in range(100):#printing the open doors.
    if doors[x]==1:
        print(x+1,end=" ")

Output:-

Efficient Approach

We can see from above that the doors which have odd no. of divisors are opened. Also, only those doors will have odd no. of divisors that are perfect squares as each no. can be written in a product of two divisors.

For eg:-n=a*b But if n is a perfect square than a can be equal to b which will result only in a single divisor.

Python Implementation:-

100doors-effective_code
Choose your Reaction!
Leave a Comment