First Bad Version - Practice Coding Problems

First Bad Version - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, bad = 4

› Output: 4

💡 Note: Versions 1, 2, 3 are good. Version 4 is the first bad version, so versions 4 and 5 are bad. Using binary search: check version 3 (good), then check version 4 (bad), so return 4.

Example 2 — First Version Bad

$ Input: n = 1, bad = 1

› Output: 1

💡 Note: Only one version exists and it's bad, so return 1.

Example 3 — Last Version Bad

$ Input: n = 3, bad = 3

› Output: 3

💡 Note: Versions 1 and 2 are good, version 3 is the first (and only) bad version.

Constraints

1 ≤ bad ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Range of versions [1, 2, ..., n] with unknown first bad version

Process

Use binary search to efficiently locate the boundary

Output

Return the first version that is bad

Key Takeaway

🎯 Key Insight: The versions form a sorted pattern (good, good, ..., bad, bad) perfect for binary search

Asked in

f Facebook 45 G Google 38 M Microsoft 32 a Amazon 28

The key insight is recognizing this as a binary search problem on a sorted pattern: good versions followed by bad versions. The optimal approach uses binary search to minimize API calls. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Check each version from 1 to n until finding the first bad one
Binary Search	O(log n)	O(1)	Use binary search to efficiently narrow down the first bad version

Linear Search — Algorithm Steps

Start from version 1
Check each version using isBadVersion()
Return the first version that is bad

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Check

Begin checking from version 1

Sequential Check

Check each version until first bad found

Found Result

Return first bad version

Code -

solution.c — C

#include <stdio.h>

int firstBad;

// Mock API for testing
int isBadVersion(int version) {
    return version >= firstBad;
}

int solution(int n) {
    for (int version = 1; version <= n; version++) {
        if (isBadVersion(version)) {
            return version;
        }
    }
    return n;
}

int main() {
    int n;
    scanf("%d", &n);
    firstBad = (n / 2 == 0) ? 1 : n / 2;
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we check all n versions sequentially

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for loop variables

✓ Linear Space

156.0K Views

High Frequency

~15 min Avg. Time

4.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler