EggDropping finds the minimum number of attempts needed to find the critical floor with `eggs` number of eggs and `floors` number of floors
(eggs, floors int)
| 8 | // EggDropping finds the minimum number of attempts needed to find the critical floor |
| 9 | // with `eggs` number of eggs and `floors` number of floors |
| 10 | func EggDropping(eggs, floors int) int { |
| 11 | // Edge case: If there are no floors, no attempts needed |
| 12 | if floors == 0 { |
| 13 | return 0 |
| 14 | } |
| 15 | // Edge case: If there is one floor, one attempt needed |
| 16 | if floors == 1 { |
| 17 | return 1 |
| 18 | } |
| 19 | // Edge case: If there is one egg, need to test all floors one by one |
| 20 | if eggs == 1 { |
| 21 | return floors |
| 22 | } |
| 23 | |
| 24 | // Initialize DP table |
| 25 | dp := make([][]int, eggs+1) |
| 26 | for i := range dp { |
| 27 | dp[i] = make([]int, floors+1) |
| 28 | } |
| 29 | |
| 30 | // Fill the DP table for 1 egg |
| 31 | for j := 1; j <= floors; j++ { |
| 32 | dp[1][j] = j |
| 33 | } |
| 34 | |
| 35 | // Fill the DP table for more than 1 egg |
| 36 | for i := 2; i <= eggs; i++ { |
| 37 | for j := 2; j <= floors; j++ { |
| 38 | dp[i][j] = int(^uint(0) >> 1) // initialize with a large number |
| 39 | for x := 1; x <= j; x++ { |
| 40 | // Recurrence relation to fill the DP table |
| 41 | res := max.Int(dp[i-1][x-1], dp[i][j-x]) + 1 |
| 42 | dp[i][j] = min.Int(dp[i][j], res) |
| 43 | } |
| 44 | } |
| 45 | } |
| 46 | return dp[eggs][floors] |
| 47 | } |