LeetCode #278 First Bad Version Solution & Explanation

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

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 <= 2³¹ – 1

Solution

In this problem, we need to find the first version that returns true in the API isBadVersion.

Using a for loop and starting to search from index 0 can yield the correct answer, but this may result in unnecessary time consumption.

Therefore, we will utilize binary search in our solution to achieve a time complexity of O(log n).

C# Solution

Solution1

/* The isBadVersion API is defined in the parent class VersionControl.
      bool IsBadVersion(int version); */

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int max =n;
        int min =0;

        while(min<max)
        {
            n = min+(max-min)/2;
            if(IsBadVersion(n))
            {
                max = n;
            }
            else
            {
                min = n+1;
            }
        }
        return max;
    }
}

Time Complexity: O(log n)

Java Solution

Solution1

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int max = n;
        int min = 0;

        while(min<max)
        {
            n = min+(max-min)/2;
            if(isBadVersion(n))
            {
                max = n;
            }
            else
            {
                min = n+1;
            }
        }
        return max;
    }
}

Time Complexity: O(log n)

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : First Bad Version – LeetCode

Similar Questions(binary search)

• LeetCode #34 Find First and Last Position of Element in Sorted Array Solution & Explanation
• LeetCode #35 Search Insert Position Solution & Explanation

Some Random LeetCode posts