aboutsummaryrefslogtreecommitdiff
path: root/first_bad_version.py
diff options
context:
space:
mode:
Diffstat (limited to 'first_bad_version.py')
-rw-r--r--first_bad_version.py31
1 files changed, 31 insertions, 0 deletions
diff --git a/first_bad_version.py b/first_bad_version.py
new file mode 100644
index 0000000..7633659
--- /dev/null
+++ b/first_bad_version.py
@@ -0,0 +1,31 @@
+# 278. First Bad Version
+from bisect import bisect_left
+
+"""
+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 returns whether 'version' is bad. implement a function to find the
+first bad version. you should minimise the number of calls to the api.
+"""
+
+
+class Solution(object):
+ def firstBadVersion(self, n):
+ """
+ :type n: int
+ :rtype: int
+ """
+ return bisect_left(self, True, 1, n)
+
+ def __getitem__(self, key):
+ return isBadVersion(key)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.firstBadVersion(5))
+ print(obj.firstBadVersion(1))