How should I practice Minimum Testers to Find the Poisoned Bottle?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Walleye Capital online assessment problems in FastPrep.

Is Minimum Testers to Find the Poisoned Bottle associated with Walleye Capital?

FastPrep tags this as a Walleye Capital online assessment coding practice problem when the problem catalog has that company and stage context.

Minimum Testers to Find the Poisoned Bottle

Walleye Capital● EasyFULLTIMEOA

Problem statement

A king has bottles bottles of water, and exactly one of them is poisoned. Even a tiny sip of the poisoned water is fatal, and the poison takes exactly 24 hours to take effect.

The king has only 24 hours to identify the poisoned bottle. Each tester may drink samples from multiple bottles.

Return the minimum number of testers needed to guarantee identifying the poisoned bottle.

For this exercise, assume there is time for exactly one round of tasting: every tester drinks all of their samples at the start, and after 24 hours the only thing the king learns is which testers died. When bottles = 1, no tester is needed.

The original question is the input bottles = 1000.

Function

minimumTesters(bottles: int) → int

Examples

Example 1

bottles = 1000return = 10

After one round, each tester is either alive or dead, so t testers can produce at most 2^t different outcomes. Each bottle needs its own outcome.

2^9 = 512 is too small and 2^10 = 1024 is enough. Number the bottles in binary and let tester i sip every bottle whose bit i is 1.

Example 2

bottles = 1return = 0

The only bottle must be the poisoned one, so no tester is needed.

Example 3

bottles = 9return = 4

Three testers give only 2^3 = 8 outcomes, which is fewer than 9 bottles. Four testers give 16 outcomes.

Constraints

1 <= bottles <= 10^9