First Bad Version easy

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 the failure of the quality check. You are given an API isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2

Input: n = 1, bad = 1
Output: 1

Steps

The problem can be efficiently solved using Binary Search. Here's the strategy:

  1. Initialize: Set left = 1 and right = n.
  2. Iterate: While left <= right:
    • Calculate the middle index: mid = (left + right) // 2.
    • Call isBadVersion(mid):
      • If isBadVersion(mid) is True, it means the bad version is either mid or somewhere before it. So, update right = mid - 1.
      • If isBadVersion(mid) is False, it means the bad version is somewhere after mid. So, update left = mid + 1.
  3. Return: After the loop, left will hold the first bad version.

Explanation

Binary search is the optimal approach because it dramatically reduces the number of calls to isBadVersion. Instead of linearly checking each version, it halves the search space in each iteration. This results in logarithmic time complexity.

The algorithm works because it exploits the property that all versions after the first bad version are also bad. By checking the middle version, we can determine whether the first bad version lies in the first or second half of the range. We repeatedly narrow down the search space until we find the first bad version.

Code

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

def firstBadVersion(n: int) -> int:
    left = 1
    right = n
    while left <= right:
        mid = (left + right) // 2
        if isBadVersion(mid):
            right = mid - 1
        else:
            left = mid + 1
    return left

Complexity

  • Time Complexity: O(log n). Binary search reduces the search space by half in each step.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space. No auxiliary data structures are used that scale with input size.