Algorithms for Coding Interviews in C++/

...

/

Solution: Egg Dropping Problem

Solution: Egg Dropping Problem

We'll cover the following...

Solution #1: Brute Force #

Press + to interact
#include<bits/stdc++.h> 
#include <iostream>
using namespace std; 
int eggDrop(int eggs, int floors) {
  // If there are no eggs, then there can't be any tries
  if (eggs <= 0)
    return 0;
  
  // If there are no floors, then no trials needed. OR if there is 
  // one floor, one trial needed.
  if (floors == 1 || floors == 0)
    return floors;
  // We need k trials for one egg and k floors 
  if (eggs == 1)
    return floors;
  int min = INT_MAX;
  int x, res;
  // Consider all droppings from 1st floor to kth floor and 
  // return the minimum of these values plus 1. 
  for (x = 1; x <= floors; x++) {
    res = max(eggDrop(eggs - 1, x - 1), eggDrop(eggs, floors - x));
  if (res < min)
      min = res;
  }
  return min + 1;
}
/* Driver program to test to pront printDups*/
int main() {
  int n = 2, k = 13;
  cout << "Minimum number of trials in worst case with " <<
    n << " eggs and " << k << " floors is " <<
    eggDrop(n, k) << endl;
  return 0;
}

When we drop an egg from floor x, there can be two cases: (1) The egg breaks (2) The egg doesn’t break.

  1. If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs
  2. If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of the above two cases for every floor, and choose the floor that yields the minimum number of trials.

Pseudocode #

eggDrop(eggs, floors)
  return 1 + min{max(eggDrop(eggs - 1, floors - 1), eggDrop(eggs,
...