Department of CSE LeetCode Practice Report
Problem 2: First Bad Version
a) Problem Statement
You are a product manager working with a team to release a product. The product
goes through n versions, numbered 1 to n. At some point, one version introduced a
bug. Since every version that follows a bad version is also considered bad, the goal is
to find the first version that turned bad.
An API call isBadVersion(version) is provided, which returns true if the given version
is bad and false otherwise. The task is to minimize the number of API calls and return
the first bad version. A brute-force linear scan would technically work but is too slow
given the constraint that n can be up to 2^31 - 1.
Constraints:
• 1 ≤ bad ≤ n ≤ 2³¹ − 1
• bad is guaranteed to exist within the range [1, n].
Example 1:
Input: n = 5, bad = 4
Output: 4
Reason: Versions 1, 2, 3 are good. Version 4 is the first bad version.
Example 2:
Input: n = 1, bad = 1
Output: 1
Reason: The only version itself is bad.
b) Algorithm
1. Accept n (total versions) as input. The isBadVersion API is
already available.
2. Initialize two pointers: low = 1, high = n.
3. Run a loop while low <= high:
3a. Compute mid = low + (high - low) / 2.
<Name of Student> | <USN> | Course: Analysis and Design of Algorithms
Department of CSE LeetCode Practice Report
. (Avoids integer overflow compared to (low + high) /
2.)
3b. Call isBadVersion(mid).
. If true -> mid could be the first bad version; set
high = mid - 1.
. If false -> first bad is to the right; set low = mid +
1.
4. When the loop ends, low points to the first bad version.
5. Return low.
Time Complexity: O(log n) — binary search halves the search space each step.
Space Complexity: O(1) — only constant extra space is used.
c) Code Implementation
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int low = 1;
int high = n;
while (low <= high) {
// Use this form to avoid integer overflow
int mid = low + (high - low) / 2;
if (isBadVersion(mid)) {
// mid might be the first bad; keep searching left
high = mid - 1;
}
else {
// mid is good; first bad must be to the right
low = mid + 1;
}
}
// low is now the first bad version
return low;
}
};
d) Test Cases Considered
Test Case Input Expected Output Actual Output Result
TC 1 n=5, bad=4 4 4 PASS
TC 2 n=1, bad=1 1 1 PASS
<Name of Student> | <USN> | Course: Analysis and Design of Algorithms
Department of CSE LeetCode Practice Report
TC 3 n=10, bad=1 1 1 PASS
All three test cases pass. The solution correctly handles a bad version in the middle, a
single-version input, and the edge case where the very first version is bad.
<Name of Student> | <USN> | Course: Analysis and Design of Algorithms