Programming

MAY 6, 2020
by **probeta**

This article covers the solution for the **First Bad Version Problem**. We will cover the complete code solution for it in the C++ programming language.

Consider that you are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have `n`

versions `[1, 2, ..., n]`

and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API `bool isBadVersion(version)`

that will return whether the `version`

is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

**For Example:**

```
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
```

What is an API this question talks about?

Well, putting it in simplest terms, an API is something that sends information back and forth between a website or app and a user. In our case, it is just a function which we can call as per our needs.

Now coming to the problem, all we need to do is to find the first version of the product that failed the quality check. Suppose we maintained a checklist of which product passed and which one failed, then our list would be like this -> [ true, true, true, { lots of true }, true, false, false, { lots of falses }, false ]. There exists a point from **1 to n** where the product transits from being continuously good to being continuously bad.

Does this pattern remind you of something? Which problem-solving strategy can be applied here?

The problem can be solved by iterating over all the products from **1 to n** and calling the API to check if the respective product is good or bad. But as we are asked to minimize the number of API calls, which in software development is a critical factor of an application's efficiency, we need to think of a better approach.

If the explanation above provoked the idea of binary search in your mind, then yes, you are absolutely right my friend. It is a straightforward implementation of binary search, except that instead of being given an array to use its values, we are given a function to call as per our need. So just as usual, we calculate the mid-value and then call the API `isBadVersion(mid)`

, if it returns falls, it means we are in the zone of bad products and need to shift or search space to **(mid-1)**, as **mid** is already a faulty product. We also assign this **mid** to our "`res`

" variable which keeps track of the starting index of the bad product. If the API call returns **true**, it means we are in the range of good product and now we need to shift our left index of search space to **mid+1**.

Here is the code solution for the problem:

```
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
long long int beg,last,mid;
beg = 1 , last = n;
long int pos = 1;
while(beg<=last){
// ensure you calculate mid values this way ,otherwise ,it would cause overflow
mid = beg + (last-beg)/2;
bool x = isBadVersion(mid);
if(x == true){
pos = mid;
last = mid-1;
}
else
beg = mid+1;
}
// return the first index of faulty product
return pos;
}
};
```

For any confusion, do comment below and feel free to ask.