First Bad Version

First Bad Version is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.

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

Topics and companies

Topics: Binary Search, Interactive.

Reported in interviews at Facebook.

How to practise First Bad Version on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log n) - Each iteration of the binary search halves the search space, so the number of calls to isBadVersion is logarithmic in n. time and O(1) - Only a constant amount of extra space is used for variables (left, right, mid). space.

Open First Bad Version in the code editor, or read the First Bad Version editorial for a worked solution with its approach and complexity analysis.

Where First Bad Version sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Sorted Array/List subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to First Bad Version

Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:

• Binary Search — Easy, same subpattern
• Guess Number Higher or Lower — Easy, same subpattern
• Kth Missing Positive Number — Easy, same subpattern
• Search a 2D Matrix — Medium, same subpattern
• Search Insert Position — Easy, same subpattern
• Single Element in a Sorted Array — Medium, same subpattern