aboutsummaryrefslogtreecommitdiff
path: root/first_bad_version.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-19 15:53:10 -0700
committerJack Sangdahl <[email protected]>2025-02-19 15:53:10 -0700
commitcf719c0935f5c19e902586ddedcf2ae1bc887b4a (patch)
treeac284b00882a44484c92ef54cc0f06c06a3244a5 /first_bad_version.c
parent0c94bad86ef5cad808fb5a323947b708b2163ace (diff)
downloadleetcode-cf719c0935f5c19e902586ddedcf2ae1bc887b4a.tar.gz
leetcode-cf719c0935f5c19e902586ddedcf2ae1bc887b4a.zip
278. first bad version
Diffstat (limited to 'first_bad_version.c')
-rw-r--r--first_bad_version.c32
1 files changed, 32 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
+}