New Tutorials:   KOTLIN    JAVASCRIPT    SASS/SCSS    PL/SQL  
CLOSE
   LeetCode  Algorithm  Cpp  
   Technology    Programming

LeetCode Solution - First Bad Version Problem

         
 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.

Problem Statement:

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. 

Explanation:

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.

First Bad Version Problem solution

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

Algorithm Logic:

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.

C++ Code Solution for First Bad Version Problem:

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.


RELATED POSTS



Subscribe and receive amazing posts directly in your inbox.