Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
3.1.
Code solution
3.2.
Python
4.
Frequently Asked Questions
4.1.
What is the drawback of using the brute force approach to solve this puzzle?
4.2.
What are interview puzzles?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Monkeys and the Doors

Author Yashesvinee V
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Interview Puzzles

Introduction

The Monkey and the Doors problem is a well-known interview puzzle asked frequently. Although it looks complicated at first sight, it has a very simple and easy solution. It uses the basic idea of factors and perfect squares to derive the answer.

Problem statement

There are 100 closed doors. A cage holding 100 monkeys is placed nearby. Every monkey that visits a door either opens a closed door or closes an open door. The first monkey that is let out of the cage visits and opens all the hundred doors. The second monkey that is released visits doors of the order 2, 4, 6, 8, 10…. . The third monkey released visits doors 3, 6, 9,12, 15……, and so on.

After all the monkeys from the cage are released and have opened or closed at least one door, how many doors are left open?

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

Let us understand how to solve this problem by observing the activity of doors 13, 50, and 16. 13 is a prime number, 50 is a composite number, and 16 is a perfect square.
 

illustration image

Prime and composite numbers have an even number of factors, and perfect squares have an odd number of factors. We can infer that prime and composite numbered doors end up being closed, while doors with perfect square numbers remain open. 

Since there are 10 perfect squares between 1 and 100, there are 10 numbers that have an odd number of factors. Hence, 10 doors will remain open.

Code solution

Now that we know how to solve the problem let us write some code to get the number of doors that remain open after all monkeys have been released by using the brute force approach.

All the programs shown below determine the number of factors of all numbers from 1 to 100. The variable ‘opendoors’ keeps track of the doors that will remain open in the end. If the number of factors is odd, the value of ‘opendoors’ is incremented. 

Python

Solution 1:

Count the number of factors for every number between 1 and 100 and determine if the door will be open or closed. 

The time complexity for this solution will be O(n x m) or O(n^2).

def numfact(a):
    count = 100
    for i in range(1, a+1):
        if a%i == 0:
            count += 1
    if count%2 != 0:   
        return 1
    return 0     
    
n = 100
opendoors = 0
for i in range(1, n+1):
    x = numfact(i)
    if x == 1:
        opendoors += 1
print(opendoors) 

 

Solution 2:

Since it is already determined that all the doors having perfect squares are the only ones to remain open, we can simply find the number of perfect squares that are less than 100. The time complexity for this solution will be O(n).

n = 100
opendoors = 0
for x in range(1, n+1):
    if x*x <= n:
        opendoors += 1
print(opendoors)    

Output:

10


Check out this problem - 8 Queens Problem

Frequently Asked Questions

What is the drawback of using the brute force approach to solve this puzzle?

The brute force approach is to count the number of factors for every number from 1 to 100. This involves running a for loop 100 times for 100 numbers. Hence, it is time-consuming and not efficient at all. 

What are interview puzzles?

Interview puzzles are critical thinking problems like brain teasers. Such questions may require lateral thinking and problem-solving skills. Interviewers determine if a potential employee is fit for the company by assessing their ability to solve complex problems using strategies and higher-order thinking.

Conclusion

This article extensively discusses the Monkey and the Doors problem. We hope that this blog has helped you enhance your knowledge about cracking puzzles of similar types. If you would like to learn more, check out our articles on the Coding Ninjas Library. Do upvote our blog to help other ninjas grow. Happy Coding!

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Monty Hall Problem
Next article
Ten Black and Ten White Socks
Live masterclass