iq.lab
Python starts when a code cell comes near or you run one
easyBinary search target 15 min

First bad version

Not solved yetLeetCode 278. First Bad Version

A product has versions numbered 1 to n, in release order. One release introduced a bug, and every later version carried it: once a version is bad, all versions after it are bad too.

You get n and a function is_bad(v) that returns True when version v is bad and False when it is good. At least one version is bad. Return the number of the first bad version.

Each call to is_bad is expensive (picture a full build and test run), so make as few calls as you can. The tests count them: at most 32 calls, even when n is 2,147,483,647 (that is 231 - 1). Never call is_bad with a number outside 1 to n.

The examples write is_bad as a lambda, a function written as one expression: lambda v: v >= 4 takes v and returns whether it is at least 4.

Example 1
Inputn = 5, is_bad = lambda v: v >= 4Output4

Versions 1 to 3 are good, and 4 and 5 are bad. The bug arrived in version 4.

Example 2
Inputn = 6, is_bad = lambda v: v >= 1Output1

Every version is bad, so the first bad one is version 1.

Example 3
Inputn = 1, is_bad = lambda v: v >= 1Output1

There is one version, and since at least one is bad, it is that one.

Constraints

  • 1 ≤ n ≤ 231 - 1

  • At least one version is bad, so is_bad(n) is True.

  • is_bad answers False for every version before the first bad one and True from there on.

  • At most 32 calls to is_bad per answer.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

⌘+Enter runs 0:00Python starts when a code cell comes near or you run one
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern