## Similar Problems

Similar Problems not available

# First Bad Version - Leetcode Solution

LeetCode: First Bad Version Leetcode Solution

Difficulty: Easy

Topics: binary-search

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.

Solution:

The problem statement is essentially asking us to perform a binary search on a sorted list of `n`

elements. We know that all versions after a bad version are also bad. Therefore, if version `mid`

is bad, we know that the first bad version must be in the range [1, mid]. Similarly, if version `mid`

is not bad, we know that the first bad version must be in the range [mid + 1, n]. We can use this observation to perform a binary search.

Let's start by initializing the left and right pointers to the first and last versions, respectively. We'll use a while loop to keep dividing the range in half until we find the first bad version.

```
class Solution:
def firstBadVersion(self, n):
left = 1
right = n
while left < right:
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left
```

Initially, the range is [1, n]. We calculate the midpoint `mid`

as shown above.

If `mid`

is bad, we know that the first bad version must be in the range [1, mid], so we set `right = mid`

. Otherwise, we know that the first bad version must be in the range [mid + 1, n], so we set `left = mid + 1`

.

We repeat this process until the range is reduced to a single version. At this point, we have found the first bad version.

Note that we use the expression `left + (right - left) // 2`

to calculate the midpoint. This is done to prevent integer overflow. If we use the expression `(left + right) // 2`

and `left + right`

is too large, we may get an incorrect result.

## First Bad Version Solution Code

`1`