LeetCode Notes: First Bad Version

#leetcode

Question

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

Solution One

Analysis:

The first simple solution that comes to mind is to look up and determine whether it is the bad version from back to front, until the first correct version is found, then the next version of the current correct version is the first bad version.

Code:

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        while(n){
            n--
            if(!isBadVersion(n)){
                 return n+1
            }
        }
    };
};

We can write a local function to test our code

/*
Manually specify the version number 2 and later versions are all bad versions
*/
const isBadVersion = function(version) {
      if(version >= 2) return true;
         return false
};

// Time-consuming recording
console.time();

// Output 2, find out the first bad version in version 1-4, that is version number 2
console.log(solution(isBadVersion)(4))

// Output default: 0.114990234375 ms, the number is very small, and the time-consuming is very short
console.timeEnd()

// Re-recording time-consuming
console.time();

//Output 2, find out the version number 1-(2^31-1), the first bad version, that is version number 2
console.log(solution(isBadVersion)(2 ** 31-1))

// Output default: 9251.9599609375 ms, the number is large, and it takes a long time
console.timeEnd()

We observe that when the largest number 2 ^ 31-1 is entered, the test on this machine takes more than 9 seconds. So consider whether there is space for optimization.

Solution Two

Analysis:

To optimize the first solution above, to find elements in a linear interval, we consider using binary search. Each time you get the middle number to make a judgment, and keep narrowing the range, you can quickly find the target number.

Code:

/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 * ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {

        //Special treatment, return directly when 1
        if(n === 1 || isBadVersion(1)) return 1

        // Define an interval for binary search
        let start = 1, end = n;

        // Keep shrinking the interval, and stop when the interval reaches the minimum
        while(start + 1 !== end){
            
            // core logic, take the integer number in the middle of the interval
            n = Math.floor((start + end) / 2);

            // If the middle number is the bad version, there may be a bad version before the middle number, move the interval forward
            if(isBadVersion(n)){
                end = n;
            }
            // If the middle number is not the bad version, the first bad version must be after the middle number, move the interval backward
            else{
                start = n;
            }

         }
        
        // In the while loop, the bad version number is assigned to end
        return end
    };
};

Similarly, we modify the test method, and then test the performance

/*
*
Manually specify the version number 500 and later versions are bad versions
*/
const isBadVersion = function(version) {
      if(version >= 500) return true;
         return false
};

// Time-consuming recording
console.time();

// Output 500, find the first bad version within the version number 1-1000, that is version number 500
console.log(solution(isBadVersion)(1000))

// Output default: 0.202880859375, which takes a short time
console.timeEnd()

// Re-recording time-consuming
console.time();

//Output 500, find the first bad version within the version number 1-(2^31-1), that is version number 500
console.log(solution(isBadVersion)(2 ** 31-1))

// Output default: 0.210205078125 ms, the time is still very short
console.timeEnd()

We see that the binary search algorithm can significantly improve efficiency.

Reference

Comments