The Super Egg Drop coding problem is a classic dynamic programming and binary search challenge. You are given k identical eggs and a building with n floors. There is a certain floor f (where 0 <= f <= n) such that any egg dropped from a floor higher than f will break, and any egg dropped from floor f or lower will not. Your goal is to find the minimum number of drops required to determine the value of f with certainty, in the worst-case scenario.
This is one of the most famous "Hard" problems, often asked by Goldman Sachs, Google, and Microsoft. It is designed to test a candidate's mathematical intuition and their ability to optimize dynamic programming solutions. The problem is not just about finding a way to solve it, but finding an efficient way, moving from an O(kn²) solution to O(kn log n) or even O(k log n) using advanced DP or mathematical observations. It separates candidates who can apply standard patterns from those who can derive complex optimizations.
The primary algorithmic patterns involved are Dynamic Programming and Binary Search. Initially, it looks like a standard DP: dp(k, n) = 1 + min(max(dp(k-1, i-1), dp(k, n-i))) for i from 1 to n. However, the min-max structure allows for an optimization where you use binary search to find the optimal floor i instead of iterating through all of them. Alternatively, a different DP state—dp(m, k) representing the maximum number of floors you can check with m moves and k eggs—provides a significantly faster linear or logarithmic solution.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Maximum Number That Sum of the Prices Is Less Than or Equal to K | Medium | Solve | |
| Nth Magical Number | Hard | Solve | |
| Numbers With Repeated Digits | Hard | Solve | |
| Smallest Good Base | Hard | Solve | |
| Digit Count in Range | Hard | Solve |
