[leetCode] 278. First Bad Version

🎆 Description

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

🎇 Solution

❌ approach 1 - time limit exceeded

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

        }
    };
};

You should minimize the number of calls to the API.
여기서 알 수 있듯 런타임을 더 줄여야 한다.

⭕ approach 2 - Binary Search

Since each version is developed based on the previous version, all the versions after a bad version are also bad.

여기서 알 수 있듯 한 번 불량이 발생하면 그 이후 버전은 모두 불량이다. 따라서 첫번째 불량을 찾으면 되는 것이다.

업다운 게임을 생각해보면 쉽다.
모든 버전에 중간 부분부터 불량인지를 확인했을때, 불량이 아니면 그 뒤에, 불량이면 그 전에 첫번째 불량 버전이 있을 것이다.

1. 1부터 n까지 중 중간을 탐색한다.
2. mid = first + Math.floor((last-first).2)
3. 중간버전이 불량이라면 이전 버전들을 확인해야 하므로 last = mid
4. 중간버전이 불량이 아니라면 이후 버전들을 확인해야 하므로 first = mid + 1

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let first = 1;
        let last = n;
        let mid;
        if(n === 1) return 1;
        while(first < last) {
            mid = first + Math.floor((last - first)/2);
            if (isBadVersion(mid)) {
                last = mid;
            } else {
                first = mid +1;
            }
        }
        return first;
    };
};

Reference

• https://leetcode.com/problems/first-bad-version/submissions/
• https://dev-youngjun.tistory.com/56