You are given N identical eggs and access to a building with k floors. Your task is to find the lowest floor that will cause an egg to break, if dropped from that floor. Once an egg breaks, it cannot be dropped again. If an egg breaks when dropped from the xth floor, you can assume it will also break when dropped from any floor greater than x. Write an algorithm that finds the minimum number of trial drops it will take, in the worst case, to identify this floor. For example, if N = 1 and k = 5, we will need to try dropping the egg at every floor, beginning with the first, until we reach the fifth floor, so our solution will be 5. Solution in Javascript, Java and Python
Javascript:
function minimumTrialDrops(N, k) {
// Base cases
if (k === 0 || k === 1 || N === 1)
return k;
// Initialize the minimum number of drops to Infinity
let minDrops = Infinity;
// Try dropping the egg from each floor
for (let i = 1; i <= k; i++) {
const dropsNeeded = Math.max(
minimumTrialDrops(N - 1, i - 1), // Egg breaks, check lower floors
minimumTrialDrops(N, k - i) // Egg doesn't break, check upper floors
);
minDrops = Math.min(minDrops, dropsNeeded + 1); // Increment the drop count
}
return minDrops;
}
// Example usage
const N = 1;
const k = 5;
const result = minimumTrialDrops(N, k);
console.log(result);
Java:
public class MinimumTrialDrops {
public static int minimumTrialDrops(int N, int k) {
// Base cases
if (k == 0 || k == 1 || N == 1)
return k;
// Initialize the minimum number of drops to Infinity
int minDrops = Integer.MAX_VALUE;
// Try dropping the egg from each floor
for (int i = 1; i <= k; i++) {
int dropsNeeded = Math.max(
minimumTrialDrops(N - 1, i - 1), // Egg breaks, check lower floors
minimumTrialDrops(N, k - i) // Egg doesn't break, check upper floors
);
minDrops = Math.min(minDrops, dropsNeeded + 1); // Increment the drop count
}
return minDrops;
}
public static void main(String[] args) {
int N = 1;
int k = 5;
int result = minimumTrialDrops(N, k);
System.out.println(result);
}
}
Python:
def minimum_trial_drops(N, k):
# Base cases
if k == 0 or k == 1 or N == 1:
return k
# Initialize the minimum number of drops to infinity
min_drops = float('inf')
# Try dropping the egg from each floor
for i in range(1, k + 1):
drops_needed = max(
minimum_trial_drops(N - 1, i - 1), # Egg breaks, check lower floors
minimum_trial_drops(N, k - i) # Egg doesn't break, check upper floors
)
min_drops = min(min_drops, drops_needed + 1) # Increment the drop count
return min_drops
# Example usage
N = 1
k = 5
result = minimum_trial_drops(N, k)
print(result)
The solutions use a recursive approach to find the minimum number of trial drops required. We consider two scenarios: when the egg breaks after being dropped from a certain floor and when it doesn’t break. We take the maximum of the two scenarios and find the minimum number of drops needed for each floor.
For the given input N = 1 and k = 5, all three solutions will return 5 as the minimum number of trial drops required