First Bad Version

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.

Constraint 1 <= bad <= n <= 2^31 - 1

Source

package questions

import _utils.UseCommentAsDocumentation
import utils.shouldBe


abstract class VersionControl(open val badVersion: Int) {
    fun isBadVersion(version: Int): Boolean {
        return version >= badVersion
    }

    abstract fun firstBadVersion(n: Int): Int
}

/**
 * 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.
 *
 *
 * Constraint `1 <= bad <= n <= 2^31 - 1`
 *
 * [Source](https://leetcode.com/problems/first-bad-version/)
 */
@UseCommentAsDocumentation
class Solution(override val badVersion: Int) : VersionControl(badVersion) {
    override fun firstBadVersion(n: Int): Int {
        // This is basically a binary search problem
        return binarySearch(0, n)
    }

    private fun binarySearch(low: Int, high: Int): Int {
        if (high < low) {
            return -1
        }

        // HERE: high can go as far as (2^31 - 1) so need to use Long to accommodate
        val mid = ((low.toLong() + high.toLong()) / 2).toInt()
        val midElement = mid + 1

        return if (isBadVersion(midElement)) {
            if (mid == 0 || (mid > 0 && !isBadVersion(midElement - 1))) { // also check for previous element
                // if previous element is not a bad version, then this is for sure the bad version
                mid + 1
            } else {
                // previous element was not bad version so continue checking
                binarySearch(low, mid - 1)
            }
        } else {
            binarySearch(mid + 1, high)
        }
    }
}

fun main() {
    run {
        Solution(badVersion = 1702766719).firstBadVersion(n = 2126753390) shouldBe 1702766719
    }

    run {
        Solution(badVersion = 4).firstBadVersion(n = 5) shouldBe 4
    }
}

---

View on GitHub

Updated on 2021-10-15