Sereche

 Profile Answers by Sereche 

• Jul 8th, 2012

 

Sounds like a simple binary search to me. For 100 floors, you would need at most 7 marbles to reach an answer. More generally, with n floors, you would need ceiling(Log2(n+1)) marbles.

If the floors are numbered 1 through 100, you would first drop a marble from floor 64 (2^6). If it breaks, test floor 32 (2^6+2^5); if not, test floor 96 (2^6+2^5). You would continue this process (either adding or subtracting the next-highest power of 2) until your interval is 2^0 = 1. For more information regarding this process, see

https://en.wikipedia.org/wiki/Binary_search

With only 2 marbles, you cannot conclusively answer the question. Assuming that a marble will break if dropped from the hundredth floor, you would first try a drop from floor 50, then from floor 25 or 75. This gives you an estimate range of 25 floors.


The above algorithm optimizes for minimum number of drops in the worst-case. I have heard a variant of this question where, for every drop, the experimenter must run up to the floor, then run back down to the ground to see if the marble broke (and therefore, dropping from higher floors is a more expensive test). The answer to this question is, of course, much more difficult.

Deepika B

• Jul 5th, 2013

 

One marble is enough to find. Start from the ground floor and proceed upwards. The marble will break in the floor in which will be lowest floor from which the marble will break. The time needed will be o(h) where is the height

Shahnawaz

• Sep 2nd, 2013

 

Solution when we have only two marbles

Use below sequence to find out correct floor
14,13,12,11,10,9,...........

First drop the first marbel on floor 14th,
if marbel breaks go to lower floor till 1st and use 2nd marbel. Floor on which second marbel break will be our answer.
else
go to 27th floor(14+13) drop first marble again
if marbel breaks go to lower floor till 15th floor and use 2nd marbel. Floor on which second marbel break will be our answer.
else
go to 39th floor(14+13+12)
follow the same procedure.

We can find answer in max 14 try if we have only two marbles.

Saurabh

• Sep 6th, 2013

 

U can use Binary search for this .. First start at last floor say 100 .. If it breaks ( remember we do not know how strong the marble is ) .. then go to floor 50 .. if it breaks go to 25th floor .. if it does not break, GO UP NOW .. so go to 37th floor ..... This way we can get the result in O(log n ) Time.....

lily

• Apr 15th, 2015

 

With 2 marbles:
Go to floor 50. If the marble breaks, go to floor 1 then floor 2 and so on up to floor 49 or until your marble breaks. Then the solution is the previous floor.
If the marble does not break, go to floor 75. If it breaks there, go to floor 51 and try floor 51 - 74.
If the marble does not break, go to floor 87. If it breaks there, try floors 76-86.
If the marble does not break, go to floor 93. If it breaks there, try floors 88-92.
If the marble does not break, go to floor 96. If it breaks there, try floors 94 and 95.
If the marble does not break, go to floor 98. If it breaks there, try floor 97.
If it does not break, try 99 and then 100.

Tyler

• May 20th, 2015

 

Start at floor 10. If the marble breaks start at 1. If it Doesnt go to 20: repeat for 11-19, and Repeat the process for 30,40,... to 100. Max amount of Drops will be 19: at 91. Up all the way to 100(10 drops) and 9 floors down(9 drops)