Solution: First Bad Version

Let's solve the First Bad Version problem using the Modified Binary Search pattern.

We'll cover the following

Statement

The latest version of a software product fails the quality check. Since each version is developed upon the previous one, all the versions created after a bad version are also considered bad.

Suppose you have n versions with the IDs [1,2,...,n][1, 2, ..., n], and you have access to an API function that returns TRUE if the argument is the ID of a bad version.

Find the first bad version that is causing all the later ones to be bad. Additionally, the solution should also return the number of API calls made during the process and should minimize the number of API calls too.

Constraints:

  • 1≤1 \leq first bad version ≤\leq n ≤105\leq 10^5

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach is to find the first bad version in the versions range by linear search. We traverse the whole version range one element at a time until we find the target version.

The time complexity of this approach is O(n)O(n), because we may have to search the entire range in this process. This approach ignores an important piece of information: the range of version numbers is sorted from 11 to nn. Let’s see if we can use this information to design a faster solution.

Optimized approach using modified binary search

Since the versions range is sorted, binary search is the most efficient approach for finding the first bad version. It executes in O(log⁡n)O(\log{n}) time, which is faster than the alternate linear scanning method.

Our goal is to find the first bad version by making the minimum number of calls to the API function. We use the binary search algorithm. The idea is to check the middle version to see if it’s bad. If it’s good, this means that the first bad version occurs later in the range, allowing us to entirely skip checking the first half of the range. If it’s bad, we need to check the first half of the range to find the first bad version. Therefore, we can skip checking the second half of the range.

When we go to check the identified half of the range, we use the same approach again. We check the middle version to figure out which half of the current range to check.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

Let’s start with the simplest step. Since we know the number of versions and also the versions range is sorted, we use two pointers, first and last. first will point to the first version, which is 11, and last will point to the last version which is n.

import java.util.*;
class FBVersion {
    public static int v;
    public static int[] firstBadVersion(int n) {
        int[] result = new int[2];
        // Assigning first pointer with the first version that is 1
        int first = 1;
        // Assigning last pointer with n that is the number of versions
        int last = n;
        int calls = 0;
        result[0] = first;
        result[1] = calls;
        System.out.print("\n\tVersions:  ");
        for (int x = first; x < last; x++) {
            System.out.print(x + ", ");
        }
        System.out.println(last + "\n");
        System.out.println("\tfirst: " + first);
        System.out.println("\tlast: " + last);
        return result;
    }
    // Driver code
    public static void main(String args[]) {
        int[] testCaseVersions = new int[]{38, 13, 29, 40, 23};
        int[] firstBadVersion = new int[]{28, 10, 10, 28, 19};
        for (int i = 0; i < testCaseVersions.length; i++) {
            v = firstBadVersion[i];
            System.out.println(i + 1 + ".\tNumber of versions: " + testCaseVersions[i]);
            firstBadVersion(testCaseVersions[i]);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
First Bad Version

Next, we can find the middle version’s ID. We do it in a while loop because we repeat this step until the first becomes equal to the last. We will pass the middle to the API function, which will tell us whether or not the middle version is bad.

import java.util.*;
class FBVersion {
    public static int v;
    public static boolean isBadVersion(int s) {
        return s >= v;
    }
    public static int[] firstBadVersion(int n) {
        int[] result = new int[2];
        // Assigning first pointer with the first version that is 1
        int first = 1;
        // Assigning last pointer with n that is the number of versions
        int last = n;
        int calls = 0;
        result[0] = first;
        result[1] = calls;
        System.out.print("\n\tVersions:  ");
        for (int x = first; x < last; x++) {
            System.out.print(x + ", ");
        }
        System.out.println(last + "\n");
        // Binary search to find the target version
        while (first < 2) // Now we will search the entire list
        {
            int mid = first + (last - first) / 2;
            first += 1;
            System.out.println("\n\tmid: " + mid);
            // isBadVersion() is the API function that returns true
            // or false depending upon whether the provided version ID
            // is bad or good
            if (isBadVersion(mid)) {
                System.out.println("\tVersion " + mid + " is bad, so we search in the first half of the list.\n");
            } else {
                System.out.println("\tVersion " + mid + " is good, so we search in the second half of the list.\n");
            }
        }
        result[0] = first;
        result[1] = calls;
        return result;
    }
    // Driver code
    public static void main(String args[]) {
        int[] testCaseVersions = new int[]{38, 13, 29, 40, 23};
        int[] firstBadVersion = new int[]{28, 10, 10, 28, 19};
        for (int i = 0; i < testCaseVersions.length; i++) {
            v = firstBadVersion[i];
            System.out.println(i + 1 + ".\tNumber of versions: " + testCaseVersions[i]);
            firstBadVersion(testCaseVersions[i]);
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
First Bad Version

Call the API fuction, isBadVersion, to check if whether or not that version is bad. Increment the calls variable on every API call so that at the end, we can return the number of API calls. In this way, each API call helps us divide our data set in half and narrow down the search space. Now, we just have to keep iterating and narrowing down until the version is found. Here’s how we divide the search space:

  • If the middle version is bad, we know that this is either the first bad version or that the first bad version occurred prior to this version. Therefore, we search for the first bad version from 1 to mid-1.
  • If the middle version is not bad, we need to search for the first bad version from mid+1 to n.

After we’ve found the first bad version, we will return a tuple containing first bad version and the minimum number of API calls.

The slides below illustrate how we would like the algorithm to run:

import java.util.*;
class FBVersion {
    public static int v;
    public static boolean isBadVersion(int s) {
        return s >= v;
    }
    public static int[] firstBadVersion(int n) {
        int[] result = new int[2];
        // Assigning first pointer with the first version that is 1 
        int first = 1;
        // Assigning last pointer with n that is the number of versions
        int last = n;
        int calls = 0;
        System.out.print("\n\tVersions:  ");
        for (int x = first; x < last; x++) {
            System.out.print(x + ", ");
        }
        System.out.println(last + "\n");
        // Binary search to find the target version
        while (first <= last) // Last should be equal to n. But here last = 2. Because we are calculating mid only one time here just to show how it works
        {
            int mid = first + (last - first) / 2;
            // isBadVersion() is the API function that returns true
            // or false depending upon whether the provided version ID
            // is bad or good
            if (isBadVersion(mid)) {
                last = mid - 1;
                System.out.println("\tVersion " + mid + " is bad, so we search in the first half of the list.\n");
            } else {
                first = mid + 1;
                System.out.println("\tVersion " + mid + " is good, so we search in the second half of the list.\n");
            }
            calls += 1;
            System.out.printf("\t| mid    |   first    |    last    |    calls    |\n");
            System.out.printf("\t ------------------------------------------------\n");
            System.out.printf("\t| " + mid + "     |   " + first + "       |    " + last + "      |    " + calls + "        |");
            System.out.print("\n\n\tVersions to check: ");
            for (int x = first; x < last; x++) {
                System.out.print(x + ", ");
            }
            System.out.println(last + "\n");
        }
        result[0] = first;
        result[1] = calls;
        return result;
    }
    // Driver code
    public static void main(String args[]) {
        int[] testCaseVersions = new int[] {38, 13, 29, 40, 23};
        int[] firstBadVersion = new int[] {28, 10, 10, 28, 19};
        for (int i = 0; i < testCaseVersions.length; i++) {
            v = firstBadVersion[i];
            if (i > 0) {
                System.out.println();
            }
            System.out.println(i + 1 + ".\tNumber of versions: " + testCaseVersions[i]);
            int[] result = firstBadVersion(testCaseVersions[i]);
            System.out.println("\n\tFirst bad version: " + result[0] + ". Found in " + result[1] + " API calls.");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
First Bad Version

Just the code

Here’s the complete solution to this problem:

class FBVersion extends BadVersion{
    public static int[] firstBadVersion(int n) {
        int[] result = new int[2];
        int first = 1;
        int last = n;
        int calls = 0;
        while (first <= last) {
            int mid = first + (last - first) / 2;
            if (isBadVersion(mid)) {
                last = mid - 1;
            } else {
                first = mid + 1;
            }
            calls += 1;
        }
        result[0] = first;
        result[1] = calls;
        return result;
    }
    // Driver code
    public static void main(String args[]) {
        int[] testCaseVersions = new int[]{38, 13, 29, 40, 23};
        int[] firstBadVersion = new int[]{28, 10, 10, 28, 19};
        for (int i = 0; i < testCaseVersions.length; i++) {
            v = firstBadVersion[i];
            if (i > 0) {
                System.out.println();
            }
            System.out.println(i + 1 + ".\tNumber of versions: " + testCaseVersions[i]);
            int[] result = firstBadVersion(testCaseVersions[i]);
            System.out.println("\n\tFirst bad version: " + result[0] + ". Found in " + result[1] + " API calls.");
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
First Bad Version

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. Assign two pointers at the IDs of the first and last versions.

  2. Calculate the mid and check if that mid version is bad.

  3. If the mid version is bad, search for the first bad version in the first half of the range of versions.

  4. If the mid version is good, search in the second half of the range of versions.

  5. Repeat the steps to check the mid version and to divide the range of versions in two until the first and last converge.

Time complexity

This algorithm takes O(log⁡n)O(\log{n}) time, because we keep dividing the searching space in half at each iteration, where nn is the number of versions.

Space complexity

The algorithm uses O(1)O(1) space.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.