leetcode

commit cf719c0935f5c19e902586ddedcf2ae1bc887b4a
parent 0c94bad86ef5cad808fb5a323947b708b2163ace
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 19 Feb 2025 15:53:10 -0700

278. first bad version

Diffstat:
A
first_bad_version.c
 | 
32
++++++++++++++++++++++++++++++++
A
first_bad_version.py
 | 
31
+++++++++++++++++++++++++++++++

2 files changed, 63 insertions(+), 0 deletions(-)
diff --git a/first_bad_version.c 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
@@ -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))