In: Computer Science
consider each bottle has t Label from 1 to n , and consider each
as a binary number.
e.g. 11 bottles
i.e 00000001,00000010,00000011,00000100,00000101,00000110,00000111,000001000,000001001,000001010,000001011,
Now, from the right to left , first take a drop from each of the
bottles whose rightest bit is set to '1' and deposited it in the
first cup.
next take a drop from each bottle whose 2nd bit is set '1' and
deposited it in the second cup.
Continue in similar metod through the highest bit,for
that total we need 4 cups and 4 tasters.
taster4 taster3 taster2 tester1
cup4 cup3 cup2 cup1
now we need to map the tasters to cups and map the cups to bits,
so map tasters to bits
command tasters to drink. In a month, some of your tasters will
become dead.
(e.g. taster3 and taster1 become dead)
then set the corresponding bits to 1, and all other bits to 0. The
resulting binary number
00000101 will identify the poisoned bottle.
Finally number of tasters f(n) = (int)(logn)+1 , so f(n) is
O(logn)