Hi, In this post we will be discussing the first bad version problem present on LeetCode

## Video Solution

## Problem Statement

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)`

which will return whether `version`

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

## Sample Test Cases

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.

## Problem Solution

### Brute Force Approach

To solve this problem using brute force method, we can just start iterating from version 1 to version N and stop as soon as we find a version for which the function `isBadVersion`

returns true. In the worst case, this method will run from `1`

to `N`

and will have a worst case time complexity of \(O(N)\)

### Optimized Approach

To optimize the above brute force solution, we should make an observation:

- If for any number
`X`

,`isBadVersion(X) = True`

then`X >= ans`

- If for any number
`X`

,`isBadVersion(X) = False`

then`X < ans`

This is true, because according to the problem description `isBadVersion`

function gives `true`

for any `version >= ans`

and gives `false`

for any `version < ans`

Therefore, here we can use binary search approach to solve the problem as shown in the solution below :

class Solution { public: int firstBadVersion(long long n) { long long ans = n; long long low = 1, hi = n; while (low <= hi) { long long mid = (low + hi)/2; if (isBadVersion(mid) == true) { ans = min(ans, mid); hi = mid - 1; } else { low = mid + 1; } } return (int) ans; } };