First Bad Version

Try to solve the First Bad Version problem.

We'll cover the following

Statement#

The latest version of a software product fails the quality check. Since each version is developed upon the previous one, all the versions created after a bad version are also considered bad.

Suppose you have n versions with the IDs [1,2,...,n][1, 2, ..., n], and you have access to an API function that returns TRUE if the argument is the ID of a bad version.

Find the first bad version that is causing all the later ones to be bad. Additionally, the solution should also return the number of API calls made during the process and should minimize the number of API calls too.

Constraints:

  • 1≤1 \leq first bad version ≤\leq n ≤231−1\leq 2^{31} - 1

Examples#

Created with Fabric.js 3.6.6 6 3 Input Versions 1 2 3 4 5 6 7 8 Sample example 1 n = 8

1 of 3

Created with Fabric.js 3.6.6 Input Versions 1 2 3 4 5 Sample example 2 n = 5 3 3

2 of 3

Created with Fabric.js 3.6.6 Input Versions 1 2 3 4 5 6 7 4 3 Sample example 3 n = 7

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

First Bad Version

1

What is the output if n = 10 and the first bad version is 6?

A)

6, 5

B)

6, 4

C)

6, 3

D)

6, 2

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize first to 11 and last to n.

Calculate mid as the mean of 11 and n and call the API function with mid. Increment the counter for the number of API calls.

If the API function returns TRUE which indicates that the argument is the ID of a bad version, set last to mid-1.

Else, if the API function returns FALSE, set first to mid+1.

While first <= last, repeat the steps to adjust first and last, to recalculate mid, and to call the API function.

Return the tuple containing the first bad version and the number of API calls.

Try it yourself#

Note: For each test case, the “Expected Output” column in the “Show Results” tab below will list the first bad version as well as the maximum number of calls to the API function that the correct solution will make.

Implement your solution in the following coding playground:

Python
usercode > version.py
n
bad
First Bad Version

Modified Binary Search: Introduction

Solution: First Bad Version