PrepBytes Interview Puzzle Series: Rats and Poison

999

This is really tricky.
Answer :10 (log1000 base 2)
1. You assign numbers 1-1000 to bottles in binary format. And assign rats 1-10.
2. You make the rat1 drink the bottle with 1 in the 1st digit.
3. You wait for 1hr. If rats 5,7,9 died, then 0000101010 is the bottle with poison, ie 42

answer is 10 xD

1 2 (bottle)
0 1
--> giving bottle 2 say to the rat that we have if he dies 2 is poisoned else 1.

1 2 3 4 (bottle)

0 1 1 0 1 1 0 0
--> bottle 1 given to rat2 and 3 given to both rat1 and rat2
4th is not given to any rats
if both rats dies 3rd is if rat1 dies then 2nd is and if rat2 dies bottle2 is poisoned.

1 2 3 4 5 6 (bottle)
001 010 011 100 101 110
----> rats needed are totally 3 ceil value of log base2 (6).

similarly, for 1000 bottles log base2 (1000) ie 10 rats are needed.