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 more than enough 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.
Example
For n = 2, the output should be
Bottles_1(n) = 0.2 can't be the edge floor, so the edge floor is the first one, and there's no need to throw any bottles.
For n = 3, the output should be
Bottles_1(n) = 1.The edge floor is either the first, or the second. If you throw a bottle from the second floor it either breaks, which means that the first floor is edge, or doesn't, which means that the second floor is the edge one.
Input/Output
- [time limit] 4000ms (js)
[input] integer n
The number of floors.
Constrains:
2 ≤ n ≤ 109.[output] integer
The maximum number of times you have to throw the bottles assuming you're applying the optimal strategy.
Solution
As we have unlimited bottles, we could start at the first floor and linearly go upwards. Unfortunately, that's not optimal. A much better approach is using binary search. And so it works: If we have \(n\) floors, go to the middle \(\frac{n}{2}\) and try if the bottle breaks. If it breaks go to the middle of the lower half \(\frac{n}{4}\), otherwise go to the upper half \(\frac{n}{2}+\frac{n}{4}\). That algorithm can be continued until the edge floor is found. As we get said that the \(n^\text{th}\) floor isn't the edge case, we can exclude it and as we halve the search space all the time, it leads to a logarithmic complexity. If \(n-1\) is a power of two, everything is fine, we get an integer out. But if we get a result with a fractional part, we would need exactly this fractional part as an extra test. But since we can make only discrete trials, we ceil the result in order to make it one extra jump. This leads to the following function:
\[f(n) = \left\lceil \log_2(n - 1) \right\rceil\]
Which can be implemented in quite small JavaScript function already:
Bottles_1 = n => Math.ceil(Math.log2(n - 1))
However, the verbosity of JavaScript is a bit annoying here, as it steals quite some bytes with the Math.ceil call. Let's see, if we can shrink it a bit:
\[\begin{array}{rl} & x = \lceil\log_2(n-1)\rceil\\ \Leftrightarrow & x = -\lfloor -\log_2(n-1)\rfloor\\ \Leftrightarrow & -x \leq -\log_2(n-1) < -x+1 \\ \Leftrightarrow & x \geq \log_2(n-1) > x-1 \\ \Leftrightarrow & x-1 < \log_2(n-1) \leq x\\ \Leftrightarrow & 2^{x-1} < n-1 \leq 2^x\\ \Leftrightarrow & 2^{x-1}-1 < n-2 \leq 2^x-1 \\ \Leftrightarrow & \log_2(2^{x-1}-1) < \log2(n-2) \leq \log_2(2^x-1)\\ \Leftrightarrow & \log_2(2^{x-2})<\log_2(2^{x-1}-1) < \log_2(n-2) \leq \log_2(2^x-1) < \log_2(2^x)\\ \Leftrightarrow & x-1 \leq \log_2(n-2) < x\\ \Leftrightarrow & x = \lfloor\log_2(n-2)+1\rfloor \end{array} \]
After that, our initial implementation can implemented like this in JavaScript, using the truncating feature when OR'ing together floating values:
Bottles_1 = n => Math.log2(n - 2) + 1 | 0
We can get rid of the double workaround by rewriting the equation to the following, which is not shorter, but saves one operator and operates in int32 the whole time:
Bottles_1 = n => 32 - Math.clz32(n - 2)