""" 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()
