Given N marbles and M floors, find the algorithm to find the lowest floor from which marble would break
algorithm, puzzle
Solution
Here is simple brute-force solution written in Java:
/**
* Return maximum number of floors that could be checked with given number
* of marbles and drops.
*/
private static int getMaximumFloors (int marblesCount, int dropsCount)
{
if (marblesCount == 0) return 0;
else
{
int result = 0;
for (int i = 0; i < dropsCount; i++)
{
result += getMaximumFloors (marblesCount - 1, i) + 1;
}
return result;
}
}
/**
* Return minimum number of drops that is definitely enough to check
* given number of floors having given number of marbles.
*/
private static int getMinimumDrops (int marblesCount, int floorsCount)
{
int dropsCount = 0;
while (getMaximumFloors (marblesCount, dropsCount) < floorsCount)
dropsCount += 1;
return dropsCount;
}
public static void main (String [] args)
{
System.out.println (getMinimumDrops (2, 100));
}
It should be easy to port it to C/C++.
Here are some results:
2 marbles, 100 floors -> 14
3 marbles, 100 floors -> 9
4 marbles, 100 floors -> 8
5 marbles, 100 floors -> 7
6 marbles, 100 floors -> 7
Problem
It is related to this questioN : Two marbles and a 100 story building BUT it is not the same ... We are to figure out best algorithm to figure out, strategy to minimize maximum drops required to find lowest floor .. Here is what I have on top of my mind The last marble has to be dropped in stepwise fashion Rest of the marbles will choose a hop (say hop-n) e.g.. So when N = 2, M = 100, We know that maximum drops=14 and hop-1 = the floor from which first marble will be dropped for very first time.