CareerCup

14 27 39 50 60 69 77 84 90 95 99 100
Maximum 14 throws are required.
Method:
x x+(x-1) x+(x-1)+(x-2)........100

nth term of this series nx-(1+2+3.....till(n-1))
=nx-(n)(n-1)/2


{nx-n(n-1)/2}>=100

for any value of n [1,2,3,4.....]
min value of x which satisfy the equation is 14.
so the answer is 14.
pls guide if i am wrong.

isn't it binary search until one ball breaks and then applying rethrow from lower end

max throws # 43
8 (to check where 1st ball breaks, i.e. 1->2->4->8->16->32->64->100) +
35 at max (to check if it breaks from 65 to 99)

A better solution,

Go to 14th floor and throw first ball,
if breaks, try 1st to 13th floor.
if doesn't break, go to 13(14-1) floor above i.e. on 27 th floor
if breaks, try 15th to 26th floor.
if doesn't break, go to 12th (13-1) floor above i.e. on 39th floor
........ Continue till solution ..............


The solution can always be found in maximum 14 attempts.

Its not a clear answer problem....Its answer will be algorithmic complexity terms...I feel 'netappreject' is correct!

Minimum number of throws depends on what X is.

if we drop a glass after every nth floor, if the first glass will break at (k+1)nth floor, but will not break at (kn)th floor. we will then use the second glass to find which floor between kn and (k+1)n the glass will break... by dropping it from each floor one by one between kn and (k+1)n.

so total number of throws is 100/n + n (in worst case)...
and we have to find the value of n for which the above eqauation is max...

so d/dn(100/n + n)=0

n=11....

we have to basically minimize the no. of throws so that we are able to cover the entire building that is 100 floors...

1.I throw from floor x, and it breaks hence I need to check all the x-1 floors (linearly) for the second egg to break .. i.e. if I start at x then I need x throws at least ( and we are minimizing x)

2. now observe that if I throw at x I cover x floors at first then x-1 floors then x-2 and so on... we have to minimize x such that the some of each spans reaches 100
e.g.
for x = 16
drop at 16, now have 15 drops for 1-15 (now drops left =15 (16-1))
drop at 31, now have 14 drops for 32-44 (now drops left =14(16-2))
.
.
.
.

i.e. at each step I span x + x-1 + x-2 + ...... until the sum reaches 100
in the optimal soln I should have just one drop left in the end and also just one floor to check ...
i.e. x + x-1 + x-2 + .... + 1 >=100
solving for x(min) gives 14 (ans)

i.e.
thow at 14, 28, . ... , 99, 100