Codesignal: Bottles_2

Original Problem

There is a bulding consisting of n floors.

Floor A is called an edge floor if for each floor from 1 to A inclusive if the bottle falls out of the window it does not break, and for each floor from A + 1 to n inclusive the bottle does break if you throw it out from there.

It is known that n cannot be the edge floor, and that the edge floor exists.

You have 2 bottles. Find the maximum number of times you have to throw the bottles out of the window to find edge floor, assuming that you're using the optimal strategy.

If a bottle gets broken, you can't use it anymore.

Example

Input/Output

Solution

It seems, people like this problem these days. I derived it already for an Apple interview question. Using the derivation, we can come up with this implementation for the problem:

Bottles_2 = n => Math.ceil((Math.sqrt(8 * n - 15) - 1) / 2)

In order to save some bytes, we reorder the equation a bit, use 4 as a sufficient approximation of \(15/4\) and remove the Math.ceil by adding 1 to the whole equation, which results in the following line and is okay to pass all the test cases:

Bottles_2 = n => Math.sqrt(2 * n - 4) + .5 | 0

« Back to problem overview