Binary Representation Approach


#1

We have 1000 bottles. So a maximum of 10 bits required to represent 1000 in binary format. Note that we cannot use 1000 prisoners (1 for each bottle because King wants to minimize the no. of prisoners also).

Now, arrange prisoners as per the bit positions.
Prisoner ------> 1 2 3 4 5 6 7 8 9 10
Bit Position --> 1 2 3 4 5 6 7 8 9 10

Bit is either 0 or 1(set). Since each number from 1 to 1000 has a unique binary representation, we can find out the poisoned bottle from the set bits positions.

Example: Say for bottle no. 10 --> 0000001010 is the binary representation. Here, 7th and 9th bits are set means 7th and 9th prisoners will drink that bottle. If 10th bottle is poisoned then 7th and 9th prisoners will die. Now we can find the answer.
Just think that how many maximum set bits we can get in binary representation for which decimal number is in between 1 to 1000. That will be the answer.