Problem
Consider a building with f number of floors. Suppose there are e number of identical eggs. Any egg if dropped from certain floor and above, then it breaks; if it is dropped from below, then it will not break. The task is to identify such floor with minimum number of trials. If egg does not break then it can be re-dropped in next trials.
Symbols
Let
f = number floors in the building e = number of eggs n = number of trials Fmax(e, n) = maximum number of floors that can be tested with e number of eggs and n number of trials. Solution
In the question,
Let us assume we will try floors
Now the question is: what should be the values of
This problem can be solved with following 3 approaches:
f and e are given and n i.e. optimum or minimum number of trials needs to be determined.Let us assume we will try floors
f1, f2, f3, . . . fk by assuming that egg never breaks. What this means is: first trial of egg drop is on floor f1; if it does not break then next trial of egg drop will be on floor f2 and so on up to floor fn assuming that first egg never breaks. Along with n we also need to find out the values for f1, f2, f3, . . . fk.Now the question is: what should be the values of
f1, f2, f3, . . . fk given f (number of floors) and e (number of eggs)? And how many optimum number of trials are needed? This problem can be solved with following 3 approaches:
- Dynamic Programming
- Binary Search Tree
- Direct Mathematical formula
Solution using Dynamic Programming approach
Before solving the original problem of trying to find
n given f and e let us shift our focus on determining the maximum number of floors that can be covered with n max trials and e number of eggs.The answer to the optimum number of trials needed will be the minimum value of
n for which Fmax(e, n) >= fWith e eggs and n drops, what is the value of Fmax(e, n) i.e. maximum number of floors that can be tested? And what should be the values of
f1, f2, f3, . . . fn etc.? Let us first try to determine the value for f1. On what basis should we choose f1?
All the floors are as follows:
1 2 3 4 . . . f1 (f1+1) (f1+2) (f1+3) . . . Fmax(e, n)
If egg breaks at
f1 then we will be left with: (f1-1) number of floors (e-1) number of eggs and (n-1) max trials that we can try further So we should choose f1 such that (f1-1) = Fmax(e-1, n-1)Hence f1 = 1 + Fmax(e-1, n-1) If the egg does not break at f1 then we will be left with: [ Fmax(e, n) - f1 ] number of floors e number of eggs and (n-1) max trials Hence we should choose
Fmax(e, n) such that [ Fmax(e, n) - f1 ] is equal to the maximum number of trials possible with e number of eggs and (n-1) number of trials. Hence Fmax(e, n) - f1 = Fmax(e, n-1)
Fmax(e, n) = f1 + Fmax(e, n-1) = 1 + Fmax(e-1, n-1) + Fmax(e, n-1) We have expressed the values of
f1 and Fmax
recursively with lower values for number of eggs and/or number of
trials. Hence if we solve the smaller sub-problems recursively, we can
find the value of Fmax(e, n) given e and n. And also we will be able to find the values of f2, f3, f4 . . . fn etc.Finding the value for
f2 reduces to smaller sub-problem of trying to find value of f1‘ with e number of eggs and (n-1) number of trials. The value of (f2-f1) should be equal to the maximum number of floors that can be covered with (e-1) eggs and (n-2) trials. Hence f2 = f1 + Fmax(e-1, n-2) + 1 Similarly if egg does not break at f1 & f2 but suppose it breaks at f3
then we will be left with:
(e-1) eggs and
(n-3) max trials. Hence f3 = f2 + Fmax(e-1, n-3) + 1 And so on Hence the floors in order are:
[Fmax(e-1, n-1) number of floors ] f1 [Fmax(e-1, n-2) number of floors ] f2 [Fmax(e-1, n-3) number of floors ] f3 [Fmax(e-1, n-4) number of floors ] . . . Fmax(e, n) Hence Fmax(e, n) = { ∑ Fmax(e-1,i) for i=1 to (n-1) } + n Here is Java code using Dynamic Programming approach:
{
public static void main(String args[])
{
final int nEggs = Integer.parseInt(args[0]);
final int nFloors = Integer.parseInt(args[1]);
int res = findOptNumOfDrops(nEggs, nFloors);
System.out.println("Number of drops needed for "+nFloors+" floors with "+nEggs+" eggs is : "+res);
}
private static int findOptNumOfDrops(final int nEggs, final int nFloors)
{
int nTrials = (int)(Math.log(1+nFloors)/Math.log(2.0));
int fmax = getFmax(nEggs, nTrials);
while(fmax < nFloors)
{
nTrials++;
fmax = getFmax(nEggs, nTrials);
}
return nTrials;
}
private static int getFmax(final int nEggs, final int nTrials)
{
if((0 == nEggs) || (0 == nTrials) )
return 0;
if(1 == nEggs)
return nTrials;
int fmax = 1 + getFmax(nEggs-1, nTrials-1) + getFmax(nEggs, nTrials-1);
return fmax;
}
}
we may improve above program by storing the results for Fmax so that the repeated calculations are avoided.
Solution using Binary Search Tree (BST)
This problem can also be
modeled with Binary Search Tree (BST).
In order to facilitate our
analysis, let us draw BST with slight modifications as follows:
1. If
egg breaks then child node is drawn on left down side
2. If
egg does not break then child node is drawn straight down side
If we draw BST with above
kind of representation then width of the BST represents the number of eggs. Width
of BST is equal to number of vertical columns in BST.
Note that, for full BST
drawn with above kind of representation, width = height
Any BST with f number of
nodes, drawn with above kind of representation and subjected to the constraint width of
BST <= e (number of eggs) is a solution but it may not be the
optimal solution. Hence obtaining the optimal solution is equivalent to
obtaining the arrangement of nodes in BST with minimum height subjected to the
constraint: width of BST <= e
If full BST is possible with
f number of nodes and if it also satisfies above constraint then such a full
BST is itself the solution and height of the BST is optimum number of trials required.
Even if full BST is not
possible with given number of floors (f), but if following conditions are met
then also it is a solution:
e
>= h
where h is the height of the next possible full BST
Fh-1
< f <= Fh
Where Fh is the
total number of nodes in full BST having height = h
Hence for given number of
floors, first we will have to obtain the value of h. If e >=
h then solution for optimal number of trials required
= h.
But if e
< h then optimum number of
trials required will be definitely more than h.
In the BST drawn with our
special kind of representation, every column corresponds to a particular number
of egg breaks. For example, to reach any node in the right most column, we will
need zero egg breaks. Whereas to reach any node in the left most column, we
will need (width -1) number of egg breaks.
Hence, if e
< h then we need to discard all
the nodes in columns requiring more than e number of egg breaks. And these
nodes needs to be inserted below the leaf nodes in remaining valid columns.
But if f < Fh then
we need not insert all the nodes from invalid columns. The number of nodes to be
inserted below the leaf nodes of valid columns = (total number of nodes in
invalid columns) – (Fh-f) ---- (1)
If above
figure comes negative then our task is done, the optimal number of trials
required = h. We need not perform the removal process, because we are sure that
the optimal number of trials required are at least h because we did choose h
based on condition:
Fh-1
< f <= Fh
If the difference in (1) is
a positive number then we have to perform the process of addition/insertion of
nodes. In this case, we can keep e number of columns from right side and all
the nodes from (width-e) number of left columns needs to be inserted below the
e number of right columns. Hence obtaining optimal solution reduces to finding
a way to insert these extra nodes below the leaf nodes of e number of right
columns such that the max height of the BST is minimised.
Let us consider an example
as follows:
e =
2
f =
12
for above example h = 4
because 23 -1 < f <= 24-1
Full BST with our special
kind of representation of height = 4 is shown in the image above and its
details are as follows:
Column
number
(left to right)
|
Nodes
|
Number
of nodes
|
Leaf
nodes
|
Number
of leaf nodes
|
Number
of egg breaks required to reach these nodes
|
0
|
1
|
1
|
1
|
1
|
3
|
1
|
2 3
5 9
|
4
|
3 5 9
|
3
|
2
|
2
|
4 6
7 10 11
13
|
6
|
7 11
13
|
3
|
1
|
3
|
8 12
14 15
|
4
|
15
|
1
|
0
|
This full BST has width = 4
and hence is not a valid solution because we have only 2 eggs. We need to move
the nodes from columns 0 & 1 below the leaf nodes under columns 2 & 3.
The number of nodes at
different columns follows the pattern of binomial coefficients as follows:
Number of nodes at column c
= nc = h!/(c! (h-c)!)
Where c starts from 0 and
ends at (h-1)
Hence the total number of
nodes in first two columns to be removed from full BST = n0 + n1 = 4!/(0! (4 –
0)!) + 4!/(1! (4 – 1)!) = 1 + 4 = 5
But we need not insert all
the 5 nodes, because f < Fh
Number of nodes to be inserted
below the leaf nodes of columns 2 & 3 = 5 – (Fh-f) = 5 – (15 -
12) = 2
The number of leaf nodes at
different columns also follows the pattern of binomial coefficients as follows:
Number of leaf nodes at
column c = nlc =
(h-1)!/( c! (h-1-c)! )
Hence number of leaf nodes
at columns 2 & 3 = 3!/(2! (4–1-2)!) + 3!/ (3! (4–1-3)!)= 3 + 1 = 4
Since in this case the
number of leaf nodes is more than the number of nodes to be inserted, solution
is trivial and is equal to 4 + 1 = 5
But if number of leaf nodes
is less than the number of nodes to be inserted then insertion of nodes needs
to be done iteratively and the leaf nodes at each iteration goes on increasing
as follows :
Suppose the number of leaf nodes at
valid columns = [4 6 1] and the number of nodes to be inserted = 30 then
we have to perform two iterations as follows and the height will be 2 + height
of full BST
Iteration number
|
Number of nodes that can be inserted in this iteration
=
number of leaf nodes at left most valid column
+
2 * number of leaf nodes at remaining valid columns
|
Cumulative number of nodes inserted
|
New leaf nodes at valid columns
=
Current number of leaf nodes
+
current number of leaf nodes at right column
At right most column the number of leaf nodes stays same at
all the iterations.
|
1
|
= 4 + 2*6 + 2 * 1
= 18
|
18
|
(4+6) (6+1) 1
= 10 7 1
|
2
|
= 10 + 2*7 + 2*1
= 26
|
44
|
(10+7) (7+1) 1
= 17 8 1
|
Here is the Java code written with this approach:
public class EggBST
{
public static void main(String args[])
{
final int nEggs = Integer.parseInt(args[0]);
final int nFloors = Integer.parseInt(args[1]);
int res = findOptNumOfDrops(nEggs, nFloors);
System.out.println("Number of drops needed for " + nFloors
+ " floors with " + nEggs + " eggs is : " + res);
}
private static int findOptNumOfDrops(final int nEggs, final int nFloors)
{
int nTrials = (int)(Math.log(1+nFloors)/Math.log(2.0));
int fmax = (int)Math.pow(2, nTrials) - 1;
while(fmax < nFloors)
{
nTrials++;
fmax = (int)Math.pow(2, nTrials) - 1;
}
if(nTrials <= nEggs)
return nTrials;
int extraNodes = fmax - nFloors;
int leftNodes = 0;
long kmod = fact(nTrials);
for(int i=0; i < nTrials - nEggs ; i++)
leftNodes += kmod/(fact(i)*fact(nTrials-i));
if(extraNodes >= leftNodes)
return nTrials;
if(extraNodes < leftNodes)
{
int nNodes = leftNodes - extraNodes;
int[] leafNodes = new int[nEggs];
kmod = fact(nTrials-1);
for(int i=0; i < nEggs ; i++)
leafNodes[i] = (int)(kmod/(fact(nTrials-nEggs+i)*fact(nEggs-i-1)));
int h = 0;
while(nNodes > 0)
{
h++;
for(int i=0;i < nEggs ; i++ )
{
if(i == 0)
nNodes = nNodes - leafNodes[0];
else
nNodes = nNodes - leafNodes[i] * 2;
}
for(int i=0;i < nEggs-1 ; i++)
leafNodes[i] = leafNodes[i]+leafNodes[i+1];
}
nTrials = nTrials + h;
}
return nTrials;
}
private static long fact(int n)
{
if (n == 0)
return 1;
long res = 1;
for (int i = 1; i <= n; i++)
res = res * i;
return res;
}
}
public class EggBST
{
public static void main(String args[])
{
final int nEggs = Integer.parseInt(args[0]);
final int nFloors = Integer.parseInt(args[1]);
int res = findOptNumOfDrops(nEggs, nFloors);
System.out.println("Number of drops needed for " + nFloors
+ " floors with " + nEggs + " eggs is : " + res);
}
private static int findOptNumOfDrops(final int nEggs, final int nFloors)
{
int nTrials = (int)(Math.log(1+nFloors)/Math.log(2.0));
int fmax = (int)Math.pow(2, nTrials) - 1;
while(fmax < nFloors)
{
nTrials++;
fmax = (int)Math.pow(2, nTrials) - 1;
}
if(nTrials <= nEggs)
return nTrials;
int extraNodes = fmax - nFloors;
int leftNodes = 0;
long kmod = fact(nTrials);
for(int i=0; i < nTrials - nEggs ; i++)
leftNodes += kmod/(fact(i)*fact(nTrials-i));
if(extraNodes >= leftNodes)
return nTrials;
if(extraNodes < leftNodes)
{
int nNodes = leftNodes - extraNodes;
int[] leafNodes = new int[nEggs];
kmod = fact(nTrials-1);
for(int i=0; i < nEggs ; i++)
leafNodes[i] = (int)(kmod/(fact(nTrials-nEggs+i)*fact(nEggs-i-1)));
int h = 0;
while(nNodes > 0)
{
h++;
for(int i=0;i < nEggs ; i++ )
{
if(i == 0)
nNodes = nNodes - leafNodes[0];
else
nNodes = nNodes - leafNodes[i] * 2;
}
for(int i=0;i < nEggs-1 ; i++)
leafNodes[i] = leafNodes[i]+leafNodes[i+1];
}
nTrials = nTrials + h;
}
return nTrials;
}
private static long fact(int n)
{
if (n == 0)
return 1;
long res = 1;
for (int i = 1; i <= n; i++)
res = res * i;
return res;
}
}
3. Solution using Direct Mathematical formula for Fmax
from the analysis done with Dynamic Programming approach, we already know the recursive formula for Fmax as follows:Fmax(e, n) = { ∑ Fmax(e-1,i) for i=1 to (n-1) } + n
with slight modification, it can be expressed as follows:
Above expression for Fmax is the basis for obtaining direct formula for Fmax for any value of e and n.
Let us determine Fmax for increasing values of e
Fmax(1, n) = n - this is the base condition we already know
Fmax(2, n) = { ∑Fmax(1,i) for i = 1 to n } - Fmax(1, n) + n
= ∑n – n + n
= ∑n
Fmax(3, n) = { ∑Fmax(2,i) for i = 1 to n } - Fmax(2, n) + n
= ∑∑n – ∑n + n
Fmax(4, n) = { ∑Fmax(3,i) for i = 1 to n } - Fmax(3, n) + n
= ∑∑∑n – ∑∑n + ∑n - (∑∑n – ∑n + n) + n
= ∑∑∑n - 2 ∑∑n + 2 ∑n
Fmax(5, n) = { ∑Fmax(4,i) for i = 1 to n } - Fmax(4, n) + n
= ∑∑∑∑n - 2 ∑∑∑n + 2 ∑∑n - (∑∑∑n - 2 ∑∑n + 2 ∑n) + n
= ∑∑∑∑n - 3 ∑∑∑n + 4 ∑∑n - 2 ∑n + n
. . .
In general the equation for Fmax(e,
n) can be obtained by finding the coefficients for different summations as
follows:
Number
of eggs
|
Coefficients
of summations
|
1
|
1
Hence Fmax(1, n) = n
|
2
|
1 1 --- append 1 to the right side of previous
coefficients [1]
- 1
= 1 0
Hence Fmax(2,
n) = ∑n
|
3
|
1 0 1
- 1 0 --- subtract previous coefficients
=
1 -1
1 --- result for new coefficients
Hence Fmax(3, n) = ∑∑n - ∑n + n
|
4
|
1 -1
1 1
-
1 -1 1
=
1
-2 2 0
Hence Fmax(4, n) = ∑∑∑n – 2 ∑∑n + 2 ∑n
|
5
|
1
-2 2 0
1
- 1
-2 2 0
= 1 -3 4
-2 1
Hence Fmax(5, n) = ∑∑∑∑n – 3 ∑∑∑n + 4 ∑∑n – 2 ∑n + n
|
…
|
…
|
The formula for ∑∑∑
… k times sum … ∑ n = n (n+1) (n+2) … (n+k-1) / (k+1)!
Hence the procedure for obtaining the value of optimum number of required drops for given e number of eggs and f number of floors is as follows:
Now let us consider specific cases of e =2, 3, 4 for understanding the way to obtain solution using Mathematical approach:
Hence the procedure for obtaining the value of optimum number of required drops for given e number of eggs and f number of floors is as follows:
- Based on given value for e, first obtain the formula for Fmax in terms of n.
- Start with log2(1+f) as a value for n and determine value of Fmax. Go on incrementing the value of n till Fmax < f. When Fmax >= f then the value of n is the answer for optimum number of trials required.
Now let us consider specific cases of e =2, 3, 4 for understanding the way to obtain solution using Mathematical approach:
2 eggs case
Let us solve the puzzle for 2 eggs case. Let us first obtain the formula for Fmax(2, n) i.e. maximum number of floors that can be covered with
2 eggs and n number of max trials.Fmax(2, n) = { ∑Fmax(1,i) for i = 1 to n } - Fmax(1, n) + n = ∑n + n - n = ∑n = n(n+1)/2 Alternatively, from the table for determination of coefficients for summations, we already know the coefficients in case of e=2 are : [1 0 ] and hence we will directly obtain the same above formula.Note: We know
Fmax(1,i) = i because with one egg and i number of trials we can cover at the most i number of floors. Hence, given 2 eggs and max n number of trials, we can cover at the most
n(n+1)/2 number of floors. Hence the problem of finding optimum number of trials given
2 eggs and f number of floors reduces to finding the value of n such that:n(n+1)/2 >= f
The minimum value of
n that satisfies above condition will be the answer. If it comes in fraction then we have to round it up.And the floor numbers are as follows:
f1 = 1 + Fmax(1, n-1) = 1 + n-1 = n f2 = f1 + Fmax(1, n-2) + 1 = n + (n–2) + 1 = n + (n-1) f3 = f2 + Fmax(1, n-3) + 1 = n + (n-1) + (n–3) + 1 = n + (n-1) + (n–2) . . . Fmax(2, n) = n + (n - 1) + (n – 2) + . . . + 1 = n(n+1)/2 Given a building with 100 floors and 2 eggs, the optimum number of trials needed are :
14 because it is the minimum integer value of n that satisfies the condition n(n+1)/2 >= 100. And the floor numbers are :
f1 = 1 + Fmax(1, 13) = 1 + 13 = 14 f2 = f1 + Fmax(1, 12) + 1 = 14 + 12 + 1 = 27 f3 = f2 + Fmax(1, 11) + 1 = 27 + 11 + 1 = 39 f4 = f3 + Fmax(1, 10) + 1 = 39 + 10 + 1 = 50 f5 = f4 + Fmax(1, 9) + 1 = 50 + 9 + 1 = 60 f6 = f5 + Fmax(1, 8) + 1 = 27 + 8 + 1 = 69 f7 = f6 + Fmax(1, 7) + 1 = 39 + 7 + 1 = 77 f8 = f7 + Fmax(1, 6) + 1 = 14 + 6 + 1 = 84 f9 = f8 + Fmax(1, 5) + 1 = 27 + 5 + 1 = 90 f10 = f9 + Fmax(1, 4) + 1 = 39 + 4 + 1 = 95 f11 = f10 + Fmax(1, 3) + 1 = 39 + 3 + 1 = 99 f12 = f11 + Fmax(1, 2) + 1 = 39 + 2 + 1 = 102 stop here & perform trial for 100 instead. f13 = f12 + Fmax(1, 1) + 1 = 39 + 1 + 1 = 104 f14 = f13 + Fmax(1, 0) + 1 = 39 + 0 + 1 = 105 Notice that since 100 < 102, we will have to try from f1 to f11 and then last try for floor 100.
Although the count of trials at this level is only 12, but still the optimum number of trials required are 14. 3 eggs case
Now let us determine Fmax for the 3 eggs case
The floors in order can be expressed as follows:
[Fmax(2, n-1) number of floors ] f1 [Fmax(2, n-2) number of floors ] f2 [Fmax(2, n-3) number of floors ] f3 [Fmax(2, n-4) number of floors ] . . . Fmax(3, n) We already know that the coefficients of summations in case of e=3 are [1 -1 1]
Hence Fmax(3, n) = ∑∑n - ∑n + n
= n(n+1)(n+2)/6 - n(n+1)/2 + n
= n/6 [ (n+1)(n+2) - 3(n+1) + 6 ]
= n/6 [ n*n+3n+2 -3n-3 + 6 ]
= n/6 [ n*n + 5 ]
= [n*n*n + 5n]/6
Hence, given 3 eggs and max n number of trials, we can cover at the most
[ n*n*n + 5n ] / 6 number of floors. Hence the problem of finding optimum number of trials given
3 eggs and f number of floors reduces to finding the value of n such that:[ n*n*n + 5n ]/6 >= f
The minimum value of
n that satisfies above condition will be the answer. If it comes in fraction then we have to round it up.And the floor numbers are as follows:
f1 = 1 + Fmax(2, n-1) = 1 + n(n-1)/2 f2 = f1 + Fmax(2, n-2) + 1 = 2 + n(n-1)/2 + (n-1)(n-2)/2 f3 = f2 + Fmax(2, n-3) + 1 = 3 + n(n-1)/2 + (n-1)(n-2)/2 + (n-2)(n-3)/2 . . . Fmax(3, n) = [ n*n*n + 5n ]/6 Given a building with
100 floors and 3 eggs, the optimum number of trials needed are : 9 because it is the minimum integer value of n that satisfies the condition:[ n*n*n + 5n ]/6 >= 100. And the floor numbers are :
f1 = 1 + Fmax(2, 8) = 1 + 8*9/2 = 37 f2 = f1 + Fmax(2, 7) + 1 = 37 + 7*8/2 + 1 = 66 f3 = f2 + Fmax(2, 6) + 1 = 66 + 6*7/2 + 1 = 88 f4 = f3 + Fmax(2, 5) + 1 = 88 + 5*6/2 + 1 = 104 stop here & perform trial for 100 instead. f5 = f4 + Fmax(2, 4) + 1 = 104 + 4*5/2 + 1 = 115 f6 = f5 + Fmax(2, 3) + 1 = 115 + 3*4/2 + 1 = 122 f7 = f6 + Fmax(2, 2) + 1 = 122 + 2*3/2 + 1 = 126 f8 = f7 + Fmax(2, 1) + 1 = 126 + 1*2/2 + 1 = 128 f9 = f8 + Fmax(2, 0) + 1 = 134 + 0 + 1 = 129 Notice that since 100 > 104, we will have to try from f1 to f3 and then last try for floor 100.
Although the count of trials at this level is only 4, but still the optimum number of trials required are 9.
4 eggs case
Now let us determine Fmax for the 4 eggs case
The floors in order can be expressed as follows:
[Fmax(3, n-1) number of floors ] f1 [Fmax(3, n-2) number of floors ] f2 [Fmax(3, n-3) number of floors ] f3 [Fmax(3, n-4) number of floors ] . . . Fmax(4, n)
We already know that the coefficients of summations in case of e=4 are [1 -2 2 0]
Hence Fmax(4, n) = ∑∑∑n - 2 ∑∑n + 2 ∑n
= n(n+1)(n+2)(n+3)/24 - 2 n(n+1)(n+2)/6 + n(n+1)
= n(n+1)/24 [ (n+2)(n+3) - 8(n+2) + 24 ]
= n(n+1)/24 [ n*n+5n+6 -8n-16 + 24 ]
= n(n+1)/24 [ n*n-3n+14 ]
= n[n*n*n -3n*n + 14n + n*n-3n+14 ]/24
= n [n*n*n - 2n*n + 11n + 14]/24
Hence Fmax(4, n) = ∑∑∑n - 2 ∑∑n + 2 ∑n
= n(n+1)(n+2)(n+3)/24 - 2 n(n+1)(n+2)/6 + n(n+1)
= n(n+1)/24 [ (n+2)(n+3) - 8(n+2) + 24 ]
= n(n+1)/24 [ n*n+5n+6 -8n-16 + 24 ]
= n(n+1)/24 [ n*n-3n+14 ]
= n[n*n*n -3n*n + 14n + n*n-3n+14 ]/24
= n [n*n*n - 2n*n + 11n + 14]/24
Hence, given 4 eggs and max n number of trials, we can cover at the most n[ n*n*n - 2n*n + 11n + 14]/24 number of floors.
Hence the problem of finding optimum number of trials given 4 eggs and f number of floors reduces to finding the value of n such that:
n[ n*n*n - 2n*n + 11n + 14] / 24 >= f
The minimum value of `n` that satisfies above condition will be the answer. If it comes in fraction then we have to round it up.
And the floor numbers are as follows:
f1 = 1 + Fmax(3, n-1) = 1 + [(n-1)(n-1)(n-1) + 5(n-1)]/6
f2 = f1 + Fmax(3, n-2) + 1 = f1 + [(n-2)(n-2)(n-2) + 5(n-2)]/6 + 1
f3 = f2 + Fmax(3, n-3) + 1 = f2 + [(n-3)(n-3)(n-3) + 5(n-3)]/6 + 1
. . .
Fmax(4, n) = n[ n*n*n - 2n*n + 11n + 14] / 24
Given a building with 100 floors and 4 eggs, the optimum number of trials needed are 8 because it is the minimum integer value of n that satisfies the condition:
n[ n*n*n - 2n*n + 11n + 14] / 24 >= 100
And the floor numbers are :
f1 = 1 + Fmax(3, 7) = 1 + (7*7*7+5*7)/6 = 1 + 63 = 64
f2 = f1 + Fmax(3, 6) + 1 = 64 + (6*6*6+5*6)/6 + 1 = 64 + 41 + 1 = 106 stop here and perform trial for 100 instead
f3 = f2 + Fmax(3, 5) + 1 = 106 + (5*5*5+5*5)/6 + 1 = 106 + 25 + 1 = 132
f4 = f3 + Fmax(3, 4) + 1 = 132 + (4*4*4+5*4)/6 + 1 = 132 + 14 + 1 = 147
f5 = f4 + Fmax(3, 3) + 1 = 147 + (3*3*3+5*3)/6 + 1 = 147 + 25 + 1 = 155
f6 = f5 + Fmax(3, 2) + 1 = 155 + (2*2*2+5*2)/6 + 1 = 155 + 3 + 1 = 159
f7 = f6 + Fmax(3, 1) + 1 = 159 + (1*1*1+5*1)/6 + 1 = 159 + 1 + 1 = 161
f8 = f7 + Fmax(3, 0) + 1 = 161 + 0 + 1 = 161 + 0 + 1 = 162
Notice that since 100 < 106, we will have to perform trials for f1 and 100 only.
Although the count of trials at this level is only 2, but still the optimum number of trials required are 8.
Here is the Java code for determining optimum number of drops for given eggs and given number of floors:
public class EggDropMath
{
public static void main(String[] args)
{
int nEggs = Integer.parseInt(args[0]);
int nFloors = Integer.parseInt(args[1]);
int res = GetOptimumNumOfTrials(nEggs, nFloors);
System.out.print("Optimum number of drops required = "+res);
}
private static int GetOptimumNumOfTrials(int nEggs, int nFloors)
{
if( (nEggs == 0) || (nFloors == 0) )
return 0;
if(nEggs == 1)
return nFloors;
int n = (int)(Math.log(nFloors+1)/Math.log(2));
int[] coeffs = getCoeffs(nEggs);
long sums[] = getSums(n, nEggs);
int fmax = GetFmax(coeffs, sums);
while(fmax < nFloors)
{
n++;
getNextSums(sums);
fmax = GetFmax(coeffs, sums);
}
return n;
}
private static void getNextSums(long[] sums)
{
int n = (int)sums[sums.length-1];
for(int i=0; i < sums.length ; i++)
sums[sums.length-i-1] = (sums[sums.length-i-1]*(n+i+1))/n;
}
private static long[] getSums(int n, int nEggs)
{
long[] sums = new long[nEggs];
sums[nEggs-1] = n;
for(int i = nEggs-2 ; i >= 0 ; i--)
{
sums[i] = n;
for(int j = 1 ; j < nEggs-i ; j++)
sums[i] = sums[i]*(n+j)/(j+1);
}
return sums;
}
private static int[] getCoeffs(int nEggs)
{
int[] coeffs = new int[nEggs];
coeffs[0] = 1;
for(int i = 1 ; i < nEggs ; i++)
{
coeffs[i] = 1;
for(int j=i; j > 0 ; j--)
coeffs[j] = coeffs[j]-coeffs[j-1];
}
return coeffs;
}
private static int GetFmax(int[] coeffs, long[] sums)
{
int fmax = 0;
for(int i=0;i < coeffs.length ; i++)
fmax += coeffs[i]*sums[i];
return fmax;
}
}
Hi
ReplyDeleteI don't know how to thank you for creating this detailed content. I just ran into this problem, and had no idea of all the details until I saw your post on StackOverflow. Thank you so much. I need to read this one more time, and I wonder if you would be willing to clarify a couple of points I am confused about.
Regards-
Shawn
Hello Shawn,
DeleteHappy to know that this post helped you. Sure, I will be happy to clarify your questions if I can. Please feel free to ask here or email me rushi.dm@gmail.com anything that you feel is better.
Thanks & Regards,
-Rushikesh.