FunctionRacerProblemsRace

Fewest Fuses to Find the Faulty Chip

HardMathPython, JavaScript, TypeScript, Java, C++

Exactly one of chips chips is faulty, and you find it with test fuses. A fuse can be wired to any set of chips at once. If the faulty chip is in that set, the fuse blows exactly wait seconds later and is gone. If not, the fuse can be wired again. Any number of fuses can be under test at the same time, and wiring takes no time.

Return the fewest fuses that are always enough to tell which chip is faulty within total seconds.

Example 1

chips 4
wait 10
total 10
returns 2

There is time for one round. Wire fuse A to chips 1 and 2, and fuse B to chips 1 and 3. Which fuses blow tells the four chips apart.

Example 2

chips 9
wait 10
total 20
returns 2

With two rounds a fuse has three outcomes: it blows in round one, in round two, or never. Two fuses give 9 outcomes, one per chip.

Example 3

chips 1
wait 5
total 5
returns 0

With a single chip there is nothing to test.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Math problems