CODEWITHSUNDEEP
algorithmbinary-search
Zack
Zack

Reputation: 385

Ladder/Eggs test for an infinite ladder and an infinite number of eggs

You all know the problem with the ladder and the eggs in which you need to find the heighest rung from which a dropped egg doesn't break.

The problem is explained on stackoverflow for the case with 100 rungs and 2 eggs, but how about when you have an infinite ladder? (and of course an infinite number of eggs)

How would you approach the problem in this case? Is Fibonacci search a solution?

Thank you very much for your help!

Upvotes: 0

Views: 1235

Answers (1)

user3758171
user3758171

Reputation: 171

For infinite eggs and ladder of unknown height, I would go with exponential search (check rung 1, then rung 2, then 4, 8, 16, etc.) until an egg breaks. If the rung on which the egg breaks is N, then do binary search between rungs N and N/2.

Upvotes: 5

Related Questions