C++ Coding Exercise – First Bad Version

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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Submit your solution to : https://leetcode.com/problems/first-bad-version/

Brute Force – Linear Search

1
2
3
4
5
6
7
8
9
10
11
12
13

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
 
class Solution {
public:
    int firstBadVersion(int n) {
        for (int i = 1; i <= n; i ++) {
            if (isBadVersion(i)) {
                return i;
            }
        }
    }
};

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        for (int i = 1; i <= n; i ++) {
            if (isBadVersion(i)) {
                return i;
            }
        }
    }
};

The brute force approach is to search from the begining (e.g. first version) until it meets the first bad version. You can imaging that if the input is the maximum (32-bit signed integer, 2^³¹-1 and the last version is a bad version, the algorithm will takes long time before it finds out the answer.

The following input yields the time-limit-exceeded error on the server.

Last executed input:
2126753390 versions, 1702766719 is the first bad version.

Binary Search

Binary search is great method to make O(n) to O(logn) scale. Everytime, the algorithm narrows down the search space, which guarantees the answer in reasonable timescale.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
 
class Solution {
public:
    int firstBadVersion(int n) {
        int i = 1;
        int j = n;
        int k = (i + (j - i) / 2);
        while (i < j) {
            if (isBadVersion(k)) {
                j = k - 1; // the answer is before k
            } else {
                i = k + 1; // the answer is after k
            }
            k = (i + (j - i) / 2); // narrows down the search space
        }
        return isBadVersion(i) ? i : i + 1;
    }
};

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int i = 1;
        int j = n;
        int k = (i + (j - i) / 2);
        while (i < j) {
            if (isBadVersion(k)) {
                j = k - 1; // the answer is before k
            } else {
                i = k + 1; // the answer is after k
            }
            k = (i + (j - i) / 2); // narrows down the search space
        }
        return isBadVersion(i) ? i : i + 1;
    }
};

Please note that to avoid integer overflow, we use (i + (j – i) / 2) to get the middle index.

–EOF (The Ultimate Computing & Technology Blog) —