Problem

Submissions

Hints & solutions

Discuss

First Bad Version

Easy

0/40

Average time to solve is 10m

Contributed by

2 upvotes

Asked in companies

Problem statement

You are a product manager and currently leading a team to develop a new version of a product. Unfortunately, the latest version you are working on 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 an array of N versions [1, 2, ..., N] and you want to find out the first bad version, which causes all the succeeding versions to be bad.

Consider we have a function isBadVersion(version), this will return whether the version is bad or not.

For an example, suppose n = 5, and version = 4 is the first bad version. So if the isBadVersion(3) returns false, isBadVersion(5) returns true and isBadVersion(4) also returns true, then the first bad version is 4.

You should minimize the number of calls to the API.

Note :

bool isBadVersion(version) returns true for all versions ‘V’ such that V > X, where X is the first bad version.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
Then the T test cases follow.

The first and only input line will have two space-separated integers N(total number of versions) and V(the first bad version).

Output format:

For each test case, print a single line containing a single integer denoting the first bad version.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= V <= N
1 <= N <= 100000

Where ‘T’ is the number of test cases, ‘N’ is the total number of versions we have, and ‘V’ is the version.

Time limit: 1 sec.

Sample Input 1:

1
5 4

Sample Output 1:

Explanation of Sample Input 1:

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Sample Input 2:

Sample Output 2:

1
5
1

Hint 1

Hint 2

Can you think of going through each element?

Approaches (2)

Approach 1

Approach 2

Brute-Force

The brute force approach that you might think of is to use the linear search algorithm. Checking for each version ‘V’ starting from 1 to N until you find the first bad version. That is for all versions V such that 1<= V <= N, find the value of isBadVersion and return V such that isBadVersion(V) = false and isBadVersion(V+1) = true.

Time Complexity

O(N), where ‘N’ is the total number of versions.

Assuming that the isBadVersion function takes constant time to check if a version is bad or not, this algorithm will do N-1 checks in the worst case, therefore the overall time complexity of the approach is

O(N).

Space Complexity

O(1).

Constant extra space is required.

(100% EXP penalty)

First Bad Version

Console