Today, I would like to share a fun and interesting algorithm to start your day in a good mood.

01

Origin story

There were 1000 bottles of liquid medicine, one of which was poison. If you drank a drop of it, you would die a day later.

Now provide a batch of rabbits to test poison, then how do we spend the least rabbits, the least time, to find this bottle of poison?

02

Conditions for analysis

One drop is enough to kill you. In other words, that bottle of potion can be given to more than one rabbit. It seems like a time and space decision to spend the least amount of rabbits and the least amount of time. Let’s simplify the problem first:

1. Only pursue time and find the potion as quickly as possible.

2. Only pursue space, save rabbits, time can be slow.

So from a simple point of view to assist thinking, but also for our in-depth thinking to lay a foundation.

03

Fancy try poison

The pursuit of the time

In a nutshell, it’s making rabbits. Take 1000 rabbits directly to test the poison, one rabbit is responsible for a bottle of potion. The result, of course, is 1000 rabbits, and the results come out in a day. This advantage is obvious, is fast; Disadvantages are also obvious: the use of too many rabbits, occupy resources, not environmental protection.

The pursuit of space

If we save rabbits for environmental reasons, then we can consider using 2 points. The first round is divided into 500 bottles of poison for a group, first put a rabbit, drink one drop of each bottle of potion, so you can eliminate 500 bottles. If alive, continue to use the rabbit, if dead, replace the rabbit. Let’s take the worst-case scenario: one rabbit at a time.

The next round of 250 bottles, loop iteration, 1000 – > 500 – > 250 – > 125 – > 63-32-16-8 – > > > > 4 – > 2 – > 1;

So 10 arrows, that’s 10 times, that’s 10 days. In this way, we only used 10 rabbits, which was very economical, but we had to wait too much.

Moderation in all things

Put the two together, and we don’t have to have 1,000 rabbits, or we don’t have to wait 10 days.

Turn 2 points into extra points. For example, 9 rabbits, each time can be divided into 10 parts, each round of rabbits to 9, so that the trial of 1000 bottles of potion, only need 3 days, 1000->100->10->1.

2 is rabbit, 3, 1000 – > 333 – > 111-37 – > > (12,12,13) – > (4, four, five) – > (2, 2, 1) – > 1;

The rule is also obvious, the number of days is D, divided into A, then the rabbit is A-1, potion N bottles, then D is equal to the logarithm of N with a as the base (logaN). For example, when using 2 rabbits, a is 3, which works out to be exactly 7 days, which is the same as we just calculated.

Computer thinking

Is there a better way? Short time, high efficiency.

Of course, since we can drink multiple bottles at once, we can simulate 1024 scenarios with 10 rabbits.

Number the potions from 1-1000, rabbits numbered, 1-10, 1000 bottles numbered, all converted to binary numbers, 1 is 000, 000, 0001,1000 is 111, 110, 1000.

In this case, the number one is given to the rabbit to drink a drop of the potion. Because the number is unique, so finally according to the dead rabbit, reverse combination, is the potion number.

In this way, 10 rabbits can successfully test the poison in just one day. Both space and time are the fastest.

04

Rabbit rabbit’s analyse

If you’re using 1000 rabbits, you’re sensitive to time. If it’s dichotomy, you must be a master of cost saving. If you use multiple fractions, you know how to strike a balance between space and time. If you can think of binary simulation quickly, then you must be familiar with computer 01 storage!

Is it timing? Or space? Or balance? Or is there a way to do both? I’m sure you’ll find something in your mind as it progresses.

This question is not only interesting, but also popular interview questions in big factory. It seems to be simple, but in fact, there is a clever thinking in it. It tests your way of thinking and logical ability.