PROGRAMMING INTERVIEWS

Question: You are given 2 identical eggs such that eggs always break if dropped from floors above a particular floor of a 100-storey building. You need to find that particular floor in minimum number of egg droppings.

Answer: What would be the minimum number of drops in worst case if we have only one egg. We have to drop the egg from every floor starting from 1st floor up to 100^th. So in worst case scenario, number of droppings will be 100.

And What would be the minimum number of drops in worst case if we have infinite supply of eggs. In that case, we can follow a binary search approach; drop from 50^th floor, if broken drop from 25^th else from 75^th and so on. So in this case, minimum number of drops will be 7 (log₂100) in worst case.

Coming back to original problem of 2 eggs, we need to divide the floors in some blocks but will that be optimal. For example, if we divide building in 10 floor groups, drop from 10^th floor; if egg doesn't break then drop from 20^th else start from 1 to 9. Now if the egg breaks from 20^th floor, we need to check only for floors 11^th to 19^th. In worst case, there will be 19 drops for floor number 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 91, 92, 93, 94, 95, 96, 97, 98, 99.

If we want optimal results, we should divide the building such that for every additional drop, remaining max drop decreases by 1. If our starting floor for first egg is 'k', there are 2 cases:

The egg breaks:  In this case, total number of drops will be 1 + (k-1) i.e.  k as we have to drop from each floor from 1 to (k-1).

The egg doesn't break: In this case, we are remaining with (100-k) floors and for optimal performance, max number of drops should be k. Also we verified that the egg doesn't break till k floors, so we need to check floors (k+1) to 100. If we choose i^th floor for 2nd drop of first egg again and egg breaks here, then max droppings needed = 1 + (i-k) (1 for k^th floor in first attempt and (i-k) for (k+1)^st to i^th floor)

As we have discussed it should be equal to k.

k = 1 + (i-k)
i = 2k - 1

This means i^th floor is (k-1) floors above kth. So this tell us that every time, we need to go up by (f-1) floors, where f is floors went up in last drop.

This means that for minimum droppings, egg should be dropped after k floors, then (k-1) floors, then (k-2) floors and so on. The sum of this series should equal 100 and last entry in this series should be 1.

  k + (k-1) + (k-2) ... + 1 = 100
  k(k+1)/2 = 100
  k2 + k - 200 = 0;
  k2 + k + (0.5)2 = 200 + (0.5)2
  (k + 0.5)2 = 200.25
  k = 200.25 1/2 - 0.5
  k = 13.65

Since floor can not be in fraction, we need our first drop from 14t^thfloor then from (14 + 13 =) 27^th, then (27 + 12 =) 39^th and so on. Also for 2 eggs, maximum number of droppings will be 14.


How to solve for generalized case?
We can see that if we drop an egg form k^th floor, there are 2 possibilities:

egg breaks: then we have (k-1) floors and 1 less egg.
egg doesn't break: then we have (100-k) floors and same number of eggs.

We can apply this logic to any number of building and any number of floors.

Code:
A recursive solution is quite easy. If maxdrop(f, e) implies maximum drops with 'e' eggs for a 'f' floor building then:

maxdrop(F, E) = for k from 1..F minimum of
                            1 + MAX(
                                       maxdrop(F-k, E),         //if egg doesn't break
                                       maxdrop(k-1, E-1)       // if egg breaks
                                    )

but there will be many redundant calls while calculating this. So lets go for a dynamic programing approach and save previously calculated maxdrop(f, e).

#include <iostream>
using namespace std;

#define max(a,b) (a>b?a:b)

int min_num_drops(int num_floors, int num_eggs)
{
  int min_throws[num_floors+1][num_eggs+1];
  int f, e, i;
  if (num_eggs == 1)
    return num_floors;
  
  for(i=0; i<num_floors+1; i++){
    min_throws[i][1] = i;
    min_throws[i][0] = 0;
    }
    
  for(i=0; i<num_eggs+1; i++)
  {
    min_throws[0][i] = 0;
    min_throws[1][i] = 1;
  }
  
  for(e=2; e<=num_eggs; e++)
  {
    for(f=2; f<=num_floors; f++)
    {
      min_throws[f][e] = INT_MAX;
      for(i=1; i<=f; i++)
      {
        int drops = 1 + max(min_throws[i-1][e-1], min_throws[f-i][e]);
        if(drops < min_throws[f][e])
          min_throws[f][e] = drops;
      }
    }
  }
  
  return min_throws[num_floors][num_eggs];
}

int main()
{
  int num_floors, num_eggs;
  cout << "Enter number of floors: ";
  cin >> num_floors;
  cout << "Enter number of eggs: ";
  cin >> num_eggs;
  cout << "minimum number of drops: " << min_num_drops(num_floors, num_eggs) << endl;
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.