887. Super Egg Drop

Description

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 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 egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Constraints

• 1 <= K <= 100

• 1 <= N <= 10000

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: K = 1, N = 2

Output: 2

Explanation:

Drop the egg from floor 1. If it breaks, we know with certainty that F = 0. Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1. If it didn't break, then we know with certainty F = 2. Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2

Example 3

Solutions

Solution 1

/**
 * Time complexity : O(K*NlogN)
 * Space complexity : O(K*N)
 */

class Solution {
    public int superEggDrop(int K, int N) {
        int[][] memo = new int[K+1][N+1];
        return helper(K, N, memo);
    }
    
    private int helper(int eggs, int floors, int[][] memo) {
        if(eggs == 1 || floors <= 1) {
            return floors;
        }
        if(memo[eggs][floors] > 0) {
            return memo[eggs][floors];
        }
        int min = Integer.MAX_VALUE;
        int low = 1, high = floors;
        
        while(low < high) {
            int mid = (low + high)/2;
            
            int breakMove = helper(eggs-1, mid-1, memo);
            int safeMove = helper(eggs, floors-mid, memo);
            
            min = Math.min(min, 1+Math.max(breakMove, safeMove));
            
            if(breakMove == safeMove) {
                break;
            } else if(breakMove > safeMove) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        memo[eggs][floors] = min;
        return min;
    }
}

Solution 2

Solution 3

Follow up