diff options
-rw-r--r-- | first_bad_version.c | 32 | ||||
-rw-r--r-- | first_bad_version.py | 31 |
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)) |