Add 278

aeronzh · Jan 26, 2016 · 99f1cbd · 99f1cbd
1 parent da0b54d
commit 99f1cbd
Show file tree

Hide file tree

Showing 2 changed files with 55 additions and 0 deletions.
diff --git a/problems/278-first-bad-version/index.js b/problems/278-first-bad-version/index.js
@@ -0,0 +1,53 @@
+/**
+ * https://leetcode.com/problems/first-bad-version/
+ *
+ * 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 will return whether version is bad.
+ * Implement a function to find the first bad version.
+ * You should minimize the number of calls to the API.
+ *
+ * Credits:
+ * Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
+ */
+
+/**
+ * Definition for isBadVersion()
+ *
+ * @param {integer} version number
+ * @return {boolean} whether the version is bad
+ * isBadVersion = function(version) {
+ *     ...
+ * };
+ */
+
+/**
+ * @param {function} isBadVersion()
+ * @return {function}
+ */
+var solution = module.exports = function (isBadVersion) {
+  /**
+   * @param {integer} n Total versions
+   * @return {integer} The first bad version
+   */
+  return function (n) {
+    var min = 1;
+    var max = n;
+    var mid = Math.floor((min + max) / 2);
+    while (max > min) {
+      if (isBadVersion(mid)) {
+        max = mid;
+      } else {
+        min = mid + 1;
+      }
+      mid = Math.floor((min + max) / 2);
+    }
+    return mid;
+  };
+};
diff --git a/problems/278-first-bad-version/testcases.js b/problems/278-first-bad-version/testcases.js
@@ -0,0 +1,2 @@
+module.exports = [
+];