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.
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)
You can also try this code with Online Python Compiler
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)
You can also try this code with Online Python Compiler
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.
46+ registered 