First Bad Version easy

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. Due to this, you have to go back to the previous versions. You have n versions numbered from 1 to n. You are given an API 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

Steps

The problem essentially asks us to find the first element in a sorted array (versions) that satisfies a condition (isBadVersion). A classic binary search approach is highly efficient for this. Here's the breakdown:

1. Initialization: Set left to 1 and right to n.
2. Iteration: While left is less than or equal to right:
   • Calculate the middle index mid as (left + right) / 2.
   • Call isBadVersion(mid).
   • If isBadVersion(mid) is true: This means the bad version is either mid or somewhere before it. Update right to mid - 1.
   • If isBadVersion(mid) is false: This means the bad version is after mid. Update left to mid + 1.
3. Result: After the loop, left will point to the first bad version. Return left.

Explanation

Binary search significantly reduces the number of calls to isBadVersion. Instead of linearly checking each version, it halves the search space in each iteration. This results in a logarithmic time complexity. The algorithm efficiently narrows down the search range until it isolates the first bad version.

Code

/* The isBadVersion API is defined in the parent class.
 * function isBadVersion(version: number): boolean {}
 */

function firstBadVersion(n: number): number {
    let left = 1;
    let right = n;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (isBadVersion(mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

To make this code executable, you'd need to provide a mock implementation of isBadVersion:

// Mock isBadVersion for testing purposes.  Replace with the actual API call in a real scenario.
function isBadVersion(version: number): boolean {
    // Replace this with your actual bad version check logic.  For example:
    return version >= 4; //  This simulates bad versions starting from version 4.
}


// Example usage
console.log(firstBadVersion(5)); // Output: 4
console.log(firstBadVersion(1)); // Output: 1

Complexity

• Time Complexity: O(log n). Binary search reduces the search space by half in each iteration.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.