**Register Now!**

955 reads

by Nicola MoroDecember 2nd, 2023

Daily Coding Problem 24

Welcome back with another problem to solve! Today, we are dealing with eggs falling from rooftops with this really nice problem, which will involve two possible solutions: one pretty naive and a more clever one. This last one will also give us the chance to talk about a quite famous algorithm.

As always, today’s problem is provided by the wonderful newsletter

Enough talking then; let’s see the problem!

This problem was asked by Goldman Sachs in a job interview. Let’s see the problem.

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`

.

So, we are given some eggs to throw from different floors of a building. We are sad that from a certain floor (which we will call `targetFloor`

), eggs thrown out do not break when falling to the ground.

From that floor to every floor below it, the eggs won’t break when thrown out from the window. What we are asked to do is to find an efficient method to find the `targetFloor`

.

As anticipated, we’ll see two methods to solve this: a really simple one, which will brute force the solution out, but it will not be efficient. The second one will be much more efficient and will try to solve the problem by breaking the least number of steps.

It will also give us the chance to talk about a really famous and important algorithm; one of those you need to know to do … basically anything!

To start off, we need to set up a bit of environment, namely the building and the `targetFloor`

. To create the building, we simply create an array containing the numbers of the floors, from the ground floor to the nᵗʰ floor. Then, we generate a random number which will be our `targetFloor`

.

We’ll write this problem in Go once again: simple enough to be readable, but complex enough to understand the inner mechanics.

We first create the array which will serve as our building: we can give it the size we want, the greater the size, the higher the building will be. After that, we create an instance of the `targetFlor`

using the `math/rand`

module built in Go.

Basically, we create a new random integer between 0 and the height of the building (… the length of the array :D) using as a source the current time.

Of course, the simplest solution possible would be to throw each egg on each floor out, so to see on which floor the eggs start to break. Since we have a variable containing that information, one could simply do a for loop to solve the problem:

While this is the simplest solution, it is unfortunately highly inefficient. Imagine if the right floor is the top one: one must break 100.000 eggs to solve the problem: that would be a huge omelet but quite a waste!

Generally speaking, this solution has a time complexity of O(n) because the complexity of the solution grows linearly to the complexity of the input problem. This is not the most efficient solution we could think of though.

Let’s think about an efficient solution then. Instead of walking floor by floor breaking each egg on each floor, we could take a guess and, based on the result of that guess, adjust the next guess.

Here’s an example: suppose we have a building with 10 floors, and the `targetFloor`

is floor 7 (we don’t know that, of course). We could take the following guesses:

Basically, we guess that the `targetFloor`

is the middle floor of the building. We throw the egg from there, and the possible outcomes are two:

- the egg breaks, meaning that we are too high. We can discard the floor higher than this one, included, and keep going on with our guesses.

- The egg does not break, meaning that we are too low or on the correct floor. We discard every floor lower than this one, included, and

Given this, we now take another educated guess about the middle floor or the “remaining” building, and apply the same strategy seen above. We can go on with this approach until we are left with one floor.

If you happen to recognize this approach, you are perfectly right: this is simply a **binary search** applied to a “real world” problem. Binary search is a simple and neat **divide-and-conquer** algorithm, meaning that at each step, the size of the problem gets halved until we find the solution.

This means that this algorithm, compared to the previous one, is way faster. Let’s see the code!

Let’s take a deeper look. The binary search function takes in 4 arguments:

`overArray`

, an array of integers, which is the building we are looping over;

`bottom`

, the bottom index of the building;

`top`

, the top floor index of the building;

`breakFloor`

, the variable holding`targetFloor`

to check if we can find it in the building.

After that, we loop over the building while `bottom`

is lower than `top`

: in binary search, when the two positional arguments interlace and swap, it means that the searched element was not found.

Therefore, if the algorithm ends up in this situation, the loop ends and we return `-1`

, meaning that the element we are looking for was not present in the array. If we are still searching for the element, we apply what is shown in the image above.

We calculate the `middlePoint`

element as the floor between `bottom`

, and `top`

and we check if `middlePoint == breakFloor`

. If it is, we return the `middlePoint`

as result.

If it’s not, we adjust `bottom`

or `top`

accordingly: if `middlePoint`

is greater than `breakFloor`

, it means we are too high on the building so we lower our prediction by setting the `top`

possible floor to `middlePoint — 1`

.

If `middlePoint`

is smaller than `breakFloor`

, we adjust our `bottom`

by setting is as `middlePoint+1`

.

Now to check everything, in the `main`

function, we generate the environment as before, and create a new variable called `bsFloor`

which will hold our result.

To confirm that our algorithm brought us to the right result, we print out both `bsFloor`

and `targetFloor`

, which was previously generated randomly.

As we anticipated before, this algorithm is way faster than the linear one. Since we halve the building at each step, we can find the correct floor in log₂(n) where n is equal to `len(building)`

.

This means that the time complexity of this algorithm is **O(log(n))**. To give you some comparison between the linear solution and this last one, if the building has 100 floors, the linear algorithm takes in the worst case 100 iterations, while the binary search algorithm takes log₂100 = 6.64, so 7 iterations.

Also, this last one is increasingly more efficient than the linear one because the more the building grows, the more the binary search is efficient. For a building with 1.000.000.000 floors, the linear one takes 1.000.000.000 steps, while the binary one takes log₂1.000.000.000 = 29.9, so 30 steps. A huge improvement!

This is it! I hope you enjoyed the article as much as I had fun trying to solve the challenge! If so, please leave a clap or two, it would be a great support! If you like these types of articles and want to see more, follow the page as I release this type of content every time I can.

Finally, if you found this article interesting or helpful and would like to contribute by offering a coffee, feel free to do so on my

And, as always, thanks for reading!

**Nicola**

*Also published here*

L O A D I N G

. . . comments & more!

. . . comments & more!