First Bad Version
You have been working on a key feature for your company's application, but after coding for months, you realize you need a break and decide to go on vacation. When you return, you pull all the latest code from the main branch into your feature branch... But there's an issue — the code is now broken.
You know that your code was working before you left, but one of the commits introduced from the main branch causes a bug with your feature (womp womp).
You know that all the commits before the one that caused the bug must still work, but then any of the commits after the breaking change was added must all be broken. It must look something like the following:
[good, good, good, good, bad, bad, bad]
You also have a helper function isBadVersion where you invoke it with a version number, and the function will return a boolean false if the version is working or true if the version is broken.
The input to the solution function is an integer that represents the total number of versions, and the output will be the first version that's broken.
Write a function firstBadVersion that returns the version number of the first commit that is broken.
So if the input is 100, there are 100 total versions. We need to determine the version between 1 and 100 that represents the first broken commit.
Breakdown
Approach and test strategy
Binary search over a monotone predicate with one-based versions
Read the approach, boundary cases, and complexity
Versions run from one through n, and once a version is bad every later version is bad. Ask the provided isBadVersion predicate about a midpoint, retaining the earliest bad candidate while discarding a proven-good prefix. The task promises a bad version in its tested domain. Do not read hidden test data or linearly query every version. Compute a midpoint without overflowing fixed-width integer addition.
Cases to check
- Check n equal to one.
- Place the first bad version at one, at n, and between them.
- Use a large n that exposes an overflowing low-plus-high midpoint.
Cost model
Halving the remaining interval uses O(log n) predicate calls. An iterative implementation uses O(1) auxiliary state under the predicate's stated cost model.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
The brute force way to approach this is to start at the beginning and iterate through each item until you find the first breaking change. This solution is O(n) time, but you can do better.
The optimal solution operates in O(log n) time and O(1) space. To solve this question, you'll utilize a new approach on a core searching concept.
First Bad Version
You have been working on a key feature for your company's application, but after coding for months, you realize you need a break and decide to go on vacation. When you return, you pull all the latest code from the main branch into your feature branch... But there's an issue — the code is now broken.
You know that your code was working before you left, but one of the commits introduced from the main branch causes a bug with your feature (womp womp).
You know that all the commits before the one that caused the bug must still work, but then any of the commits after the breaking change was added must all be broken. It must look something like the following:
[good, good, good, good, bad, bad, bad]
You also have a helper function isBadVersion where you invoke it with a version number, and the function will return a boolean false if the version is working or true if the version is broken.
The input to the solution function is an integer that represents the total number of versions, and the output will be the first version that's broken.
Write a function firstBadVersion that returns the version number of the first commit that is broken.
So if the input is 100, there are 100 total versions. We need to determine the version between 1 and 100 that represents the first broken commit.