Log inSign up
hardGeeksforGeeksNot Started

Egg Dropping Puzzle

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

You are given k identical eggs and you have access to a building with n floors labeled from 1 to n.

You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break.

Each move, you may take an unbroken egg and drop it from any floor x (1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may reuse it in future moves.

Return the minimum number of moves that you need to determine with certainty what f is, in the worst case.

### Example 1 - Input: k = 1, n = 2 - Output: 2 - Explanation: Drop egg from floor 1. If it breaks, f = 0. If not, drop from floor 2. In worst case, 2 drops needed.

### Example 2 - Input: k = 2, n = 6 - Output: 3 - Explanation: Drop from floor 3. If breaks, test 1 and 2 (total 3 moves). If not, drop from 5... minimum moves in worst case is 3.

### Example 3 - Input: k = 3, n = 14 - Output: 4

Constraints:

  • 1 <= k <= 100
  • 1 <= n <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize when inverting state and answer transforms polynomial complexity into logarithmic speed.
  • Derive the floor-capacity recurrence from egg break/survive branches.
  • Implement the 1D rolling array optimization.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Minimizing attempts in the worst case with limited disposable testing tools (eggs).
  • Threshold discovery problem.

Algorithmic Decision Tree:

  • Standard DP O(k * n2) gets TLE.
  • Invert the DP state: test capacity as a function of moves.

Connected Patterns:

Super Egg DropBinary Search on AnswerGuess Number Higher or Lower II

1. Minimax Recursion with Binary Search

Intuition

For each floor x from 1 to n, take the worst case between breaking (x-1 floors below, k-1 eggs) and surviving (n-x floors above, k eggs).

Algorithm

  1. Define solve(k, n).
  2. Base Cases: if n <= 1, return n; if k == 1, return n.
  3. Initialize minAttempts = infinity.
  4. For x = 1 to n:
  5. worstCase = 1 + max(solve(k - 1, x - 1), solve(k, n - x))
  6. minAttempts = min(minAttempts, worstCase).
  7. Return minAttempts.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int memo[105][10005];
8
9int solveMinimax(int k, int n) {
10 if (n <= 1 || k == 1) return n;
11 if (memo[k][n] != 0) return memo[k][n];
12
13 int low = 1, high = n, ans = n;
14 while (low <= high) {
15 int mid = (low + high) / 2;
16 int broken = solveMinimax(k - 1, mid - 1);
17 int notBroken = solveMinimax(k, n - mid);
18
19 ans = min(ans, 1 + max(broken, notBroken));
20 if (broken < notBroken) {
21 low = mid + 1;
22 } else {
23 high = mid - 1;
24 }
25 }
26 return memo[k][n] = ans;
27}
28
29int superEggDropMinimax(int k, int n) {
30 return solveMinimax(k, n);
31}
32
33int main() {
34 int k = 2, n = 6;
35 cout << "Min Drops (Minimax + Binary Search): " << superEggDropMinimax(k, n) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(k * n^2) naive, O(k * n log n) with binary search
  • Space complexity: O(k * n) memoization

2. Inverted 2D Dynamic Programming (Moves x Eggs)

Intuition

Define dp[m][k] as the maximum number of floors that can be tested with m moves and k eggs.

Algorithm

  1. Create table dp[n + 1][k + 1] filled with 0.
  2. Initialize m = 0.
  3. While dp[m][k] < n:
  4. m++
  5. For i = 1 to k:
  6. dp[m][i] = dp[m - 1][i - 1] + dp[m - 1][i] + 1
  7. Return m.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int superEggDrop2D(int k, int n) {
7 vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
8 int m = 0;
9
10 while (dp[m][k] < n) {
11 m++;
12 for (int i = 1; i <= k; i++) {
13 dp[m][i] = dp[m - 1][i - 1] + dp[m - 1][i] + 1;
14 }
15 }
16 return m;
17}
18
19int main() {
20 int k = 2, n = 6;
21 cout << "Min Drops (Inverted 2D DP): " << superEggDrop2D(k, n) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(k * moves) <= O(k * log n) for k > 1
  • Space complexity: O(n * k)

3. 1D Array Inverted DP O(k) Space

Intuition

Maintain a 1D array dp of size k + 1. In each move, update in reverse: dp[i] = dp[i] + dp[i - 1] + 1.

Algorithm

  1. Create array dp of size k + 1 filled with 0.
  2. Initialize m = 0.
  3. While dp[k] < n:
  4. m++
  5. For i = k down to 1:
  6. dp[i] = dp[i] + dp[i - 1] + 1
  7. Return m.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int superEggDropOptimal(int k, int n) {
7 vector<int> dp(k + 1, 0);
8 int m = 0;
9
10 while (dp[k] < n) {
11 m++;
12 for (int i = k; i >= 1; i--) {
13 dp[i] = dp[i] + dp[i - 1] + 1;
14 }
15 }
16 return m;
17}
18
19int main() {
20 int k = 2, n = 6;
21 cout << "Min Drops (Optimal 1D DP): " << superEggDropOptimal(k, n) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(k * moves) <= O(k * log n)
  • Space complexity: O(k) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Minimax + Binary SearchO(k * n log n)O(k * n)Minimax over drop floor x using binary search on monotonic functions.Binary search per state
2.Inverted 2D DPO(k * moves)O(n * k)dp[m][k] = max floors testable with m moves.Matrix allocation
3.Inverted 1D DPOptimalO(k * moves)O(k)1D array updated in reverse with moves counter.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Assuming binary search always works with k eggs (binary search requires k >= log2(n); if k = 1, binary search fails on first break).

Pitfall 2:

Using the O(k * n2) naive DP that causes TLE on platforms with strict time limits.

Crucial Edge Cases to Validate:

  • k = 1: Must drop linearly from floor 1 to n (output: n).
  • n = 1: Exactly 1 drop needed.
  • k >= log2(n): Binary search is always possible; moves = ceil(log2(n + 1)).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Present the 2-egg puzzle first (triangular numbers m*(m+1)/2 >= n), then generalize to k eggs via the inverted DP formulation. This demonstrates stellar communication and mathematical intuition.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does inverting the problem to 'maximum floors testable given m moves and k eggs' drastically speed up the solution?

Back to DSA Sheet