Bad Product
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 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\
Constraints:
1 <= bad <= n <= 231 - 1
Solution
Intuitively, we know that the product versions is a sequence of good versions, followed by a group of bad versions.
This means that we are looking for the first index which isBadVersion(ans)
returns true
.
Therefore, we must update the answer when we find a smaller version that is bad, repeat until we find the smallest.
1def firstBadVersion(self, n: int) -> int:
2 left, right = 1, n
3 ans = -1
4
5 while left <= right:
6 mid = (left + right) // 2
7 if isBadVersion(mid):
8 ans = mid
9 right = mid - 1
10 else:
11 left = mid + 1
12
13 return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhich of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time