diff options
author | Jack Sangdahl <[email protected]> | 2025-02-19 15:53:10 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-19 15:53:10 -0700 |
commit | cf719c0935f5c19e902586ddedcf2ae1bc887b4a (patch) | |
tree | ac284b00882a44484c92ef54cc0f06c06a3244a5 /first_bad_version.c | |
parent | 0c94bad86ef5cad808fb5a323947b708b2163ace (diff) | |
download | leetcode-cf719c0935f5c19e902586ddedcf2ae1bc887b4a.tar.gz leetcode-cf719c0935f5c19e902586ddedcf2ae1bc887b4a.zip |
278. first bad version
Diffstat (limited to 'first_bad_version.c')
-rw-r--r-- | first_bad_version.c | 32 |
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 +} |