String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding


Finding First Bad Version

In this article, we are going to see how to solve the following searching problem in minimum time complexity? This problem can be featured in any interviews. Submitted by Radib Kar, on January 18, 2019

Problem statement

Suppose that IncludeHelp turns to be a product company & we have a product manager leading a team to develop a new product. Unfortunately, the latest version of our 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 we have n versions [1, 2, ..., n] and we want to find out the first bad one, which causes all the following ones to be bad.

Our product manager is given an API bool isBadVersion(version) which will return whether version is bad or not. He now wants to hire a programmer to implement a function to find the first bad version. There should be minimum number of calls to the API. Can you help him out?

Solution Approach

Of course this is a searching problem & for optimization we can do a binary search here. But now the question is, is there any other optimum searching method for search problem? The answer is yes.

It is binary search but the narrow down constant, K is not typically (low + high)/2 as in case of general binary search.

In this case the narrow down constant, K= low+(high-low)/2 resulting in much more optimized result.


We have already the API function bool isBadVersion(version)

Now to find the first bad version we generate another function:

low=lower bound variable
high=upper bound variable

FUNCTION findFirstBad( int low, int high)
        1.  Set mid to the narrow down constant K, low+(high-low)/2;
        2.  IF (isBadVersion(mid))  //if it is bad
            //there can be two case
            //1.    This is no 1, so thdere is no other version previously 
            //      thus these must be the first one
            //2.    The immediate previous one is not bad, thus this is 
            //      the first bad one
            IF (mid==1 || !isBadVersion(mid-1))
                Return mid;
                //narrow down high as first bad one must be before this one
            End IF-ELSE
            //since this is not bad, the lower bound must be > this version
        END IF-ELSE
        3.  If not returned from while loop, no bad version exists at all
        Return -1;

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

#define n 10

int A[n]= { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};

// declaration of isBadVersion API.
bool isBadVersion(int version){
	return A[version];

int findFirstBad(int low,int high){
		//narrow down factor
		int mid=low+(high-low)/2;
		if(isBadVersion(mid)) {
			if(mid==0 || !isBadVersion(mid-1))
				return mid+1;
	return -1;	

int firstBadVersion(int i) {
			return i+1;
			return -1;
	return findFirstBad(0,i);

int main(){
	cout<<"this is a functional problem,so main functiom hardcoded\n";
	//product versions
	//A[n]= { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
	//0=good product, 1=bad product
	cout<<"product versions are:\n";
	for(int i=0;i<n;i++){
	cout<<"First Bad version is:\n";
	return 0;


this is a functional problem,so main functiom hardcoded
product versions are:
1       good
2       good
3       good
4       good
5       good
6       good
7       bad
8       bad
9       bad
10      bad
First Bad version is:

Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.