Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0278 - First Bad Version
    0278 - First Bad Version
    0278 - First Bad Version
    0278 - First Bad Version

    0278 - First Bad Version

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/first-bad-version/

    Solution 1 - Linear Scan

    Iterate through each version from 1 to n and call isBadVersion() on each. Return the first version that returns True. Simple but inefficient for large n.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    Solution 2 - Binary Search

    Since all versions after the first bad version are also bad, the sequence of good/bad forms a sorted boundary. Use binary search to efficiently find the first bad version by halving the search space each step. If mid is bad, the first bad version is at mid or earlier. If mid is good, the first bad version is after mid.

    TimeComplexity:O(log⁡n)TimeComplexity: O(\log n)TimeComplexity:O(logn)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0278.1 - First Bad Version - Solution 1 - Linear Scan """

#####################################################################################
# Imports
#####################################################################################
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def firstBadVersion(self, n: int) -> int:
        """First Bad Version Function"""
        for i in range(1, n + 1):
            if isBadVersion(i):
                return i


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example: n = 5, bad = 4
    # isBadVersion(3) -> False
    # isBadVersion(5) -> True
    # isBadVersion(4) -> True
    # Output: 4
    print(Solution().firstBadVersion(5))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0278.2 - First Bad Version - Solution 2 - Binary Search """

#####################################################################################
# Imports
#####################################################################################
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def firstBadVersion(self, n: int) -> int:
        """First Bad Version Function"""
        left, right = 1, n
        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: n = 5, bad = 4 -> Output: 4
    # Example 2: n = 1, bad = 1 -> Output: 1
    print(Solution().firstBadVersion(5))
    print(Solution().firstBadVersion(1))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()