6 pigs for 1000 buckets -- Solution by Division into Groups & Binary Combinations

  • 0

    This is not the best solution but the basic idea is pretty straight forward: use 3 rounds to divide the buckets into smaller and smaller groups, zooming in on the one containing the poison each time, then on the last round do a search using binary state combination of the pigs that are still alive to get the exact location of the poisoned bucket. You can find a detailed explanation with visualization on my blog. It also contains some of my critiques of the method using matrices & cubes if you're interested.

    Anyway, with the above algorithm you can test a maximum of 1680 buckets using 6 pigs in one hour. It's close but not as optimal as the encoding method especially at very large number of buckets (~1 mil).

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.