LintCode: Poison Test

Poison Test



Similar Problems:


Description
Given the n bottles of water, only one bottle of water is poison, and mouse will die 24 hours later after drinking any dose of poison.
If you want to figure out that which bottle of water is poison in 24 hours, how many mice are needed to ensure to success of poison test?
(That means you can only feed each mouse once)

1<= n <=10000000

Example

Given n=3,return 2

Explanation:
Let No. 1 mouse drink No.1 water,and let No. 2 mouse drink No.2 water
If the No. 1 mouse died, it indicates that No. 1 water is poison.
If the No. 2 mouse dies, it indicates that the No. 2 water is a poison.
If it is not dead, it means that water No. 3 is poison.
Given n=6,return 3

Explanation:
Let No. 1 mice drink No. 5 and No. 6 water,let No. 2 mice  drink No. 3 and No. 4 water, and let No. 3 mice drink No. 2, No. 4 and No. 6 water .
If the mice 1, 2, and 3 are not dead, the water No. 1 is poisonous;
If the mice 1, 2 are not dead, 3 die, then the 2nd water is poisonous;
If the mice 1, 3 are not dead, 2 die, then the 3rd water is poisonous;
If the mouse 1 does not die, 2, 3 die, then the 4th water is poisonous;
If the mouse 1 dies, 2, 3 does not die, then the 5th water is poisonous;
If the mice die 1, 3, 2 are not dead, then the 6th water is poisonous;

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/poison-test
// Basic Ideas:
// Complexity: Time O(log(n)), Time O(1)
/**
 * @param n: There are n bottles of water
 * @return: Return the number of mice
 */
func getAns (n int) int {
    res, val := 0, 1
    for val < n {
        res, val = res+1, val*2
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.