aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--first_bad_version.c32
-rw-r--r--first_bad_version.py31
2 files changed, 63 insertions, 0 deletions
diff --git a/first_bad_version.c b/first_bad_version.c
new file mode 100644
index 0000000..4b87ee6
--- /dev/null
+++ b/first_bad_version.c
@@ -0,0 +1,32 @@
+// 278. First Bad Version
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+bool isBadVersion(int version);
+
+int firstBadVersion(int n) {
+ int start = 0, end = n;
+ while (end - start > 1) {
+ int mid = start + (end - start) / 2;
+ if (isBadVersion(mid))
+ end = mid;
+ else
+ start = mid;
+ }
+ return end;
+}
+
+int main() {
+ printf("%d\n", firstBadVersion(5)); // expect: 4
+ printf("%d\n", firstBadVersion(1)); // expect: 1
+}
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))