278. First Bad Version
Model: qwen2.5-coder:14b
Topics: Binary Search
FAANG asked: 1
Acceptance rate: 37.8%
Problem Breakdown
We are tasked with finding the first bad version in a sequence of versions where all subsequent versions are also bad. The API isBadVersion(version) is provided to check if a given version is bad. We need to minimize the number of calls to this API.
Inputs:
- An integer
nrepresenting the total number of versions. - A hidden function
isBadVersion(version)that returnsTrueif the version is bad, otherwiseFalse.
Outputs:
- The first bad version number.
Implicit Constraints or Tricky Edge Cases:
- If there are no bad versions (which is not possible given the problem constraints), we should return -1.
- The function should handle large values of
nefficiently due to the constraint1 <= n <= 2^31 - 1.
Intuition
A brute-force approach would involve checking each version from 1 to n sequentially until a bad version is found. This approach has a time complexity of O(n), which is inefficient given the large possible value of n.
The key insight is that since all versions after a bad version are also bad, we can use binary search to minimize the number of API calls. Binary search reduces the problem size by half with each iteration, leading to a much more efficient solution.
Approach
We will use binary search to find the first bad version:
- Initialize two pointers,
leftandright, to 1 andnrespectively. - While
leftis less than or equal toright:- Calculate the middle point
mid. - If
isBadVersion(mid)returnsTrue, it means the first bad version is atmidor beforemid. So, we move therightpointer tomid - 1. - If
isBadVersion(mid)returnsFalse, it means the first bad version is aftermid. So, we move theleftpointer tomid + 1.
- Calculate the middle point
- When the loop ends,
leftwill be pointing to the first bad version.
Complexity Analysis
- Time Complexity: O(log n) because we are using binary search to halve the search space in each iteration.
- Space Complexity: O(1) as we are only using a constant amount of extra space for variables.
Solution
def firstBadVersion(n):
left, right = 1, n
while left <= right:
mid = (left + right) // 2
if isBadVersion(mid):
right = mid - 1
else:
left = mid + 1
return left
Edge Cases Handled
- Single Version: If
nis 1, the function will correctly identify it as the first bad version. - All Versions Bad: The binary search ensures that we find the first bad version efficiently even if all versions are bad.
- No Bad Versions (Theoretical): Although not possible in this problem due to constraints, the binary search approach inherently handles cases where no bad version exists by converging on a non-existent bad version.