0
$\begingroup$

I came across following question:

There is a building with N floors. We have a balls of same property and have a breaking point of X floor. i.e, If ball dropped from X+1 floor then the ball will break. if ball is dropped from X or less than X then it wont break. Now design an algorithm to find X if N is given.

My Solution:

Drop the ball from N/2 floor. If ball breaks then X < N/2. Else X > N/2. Repeat this process till X is found. but If X is N/2+1 or N/2-1 the number of steps to find X are high.

Is there a better way to Find X?

$\endgroup$
  • 1
    $\begingroup$ You now perform binary search. Your answer is only valid if you have many balls available. Linear search is the option if you only have one ball to break :) $\endgroup$ – Hendrik Jan Dec 4 '13 at 14:03
  • 1
    $\begingroup$ The usual statement for this problem specifies a limit on how many balls you are allowed to break and its usually "light bulbs" or "eggs" instead of balls: qntm.org/bulbs. That said, if you have an unlimited supliy of balls then binary search minimizes the number of tests. $\endgroup$ – hugomg Dec 5 '13 at 4:45
0
$\begingroup$

This is the best way to Find $X$. Your algorithm is basically binary search, which is optimal in terms of comparisons.

Let $T(N)$ be the number of ball-drops required in a building with $N$ floors to find $X$. \begin{align} T(1) = & 0 & \text{(no balldrop with one floor)}\\ T(N) = & T(\frac{N}{2}) + 1& \text{(drop ball once, repeat on upper/lower half)} \\ = & T(0) + 1 + \ldots + 1 \in \mathcal{O}(\log n) \end{align}

Each floor $i$ of the $N$ floors can be represented as binary number with $\lceil \log_2N\rceil$ bits. To identify one number out of a set of $N$ numbers, you have to look at each single bit, hence this takes you $\lceil\log_2 N\rceil \in \mathcal{O}(\log n)$ comparsons. So in terms of complexity, there is no better way to find $X$.

Of course, you could check one floor above as well as one floor under the current floor, which covers the cases $X=\frac{N}{2}+1$ and $X=\frac{N}{2}-1$, respectively. But you this does not improve your algorithm in terms of $\mathcal{O}$ complexity. Furthermore, you can always construct another worst case for you algorithm, since $N$ is unbounded: The improved algorithm performs poorly when $X=\frac{N}{2}-2$ or $X=\frac{N}{2}+2$. So you could add those cases as well. But then $X=\frac{N}{2}-3$ and $X=\frac{N}{2}+3$ becomes a problem ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.