LeetCode 278: First Bad Version

-

Question

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 minimize the number of calls to the API.

 

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

Input: n = 1, bad = 1
Output: 1

 

Solution

/**
* Definition for isBadVersion()
*
* @param {integer} version number
* @return {boolean} whether the version is bad
* isBadVersion = function(version) {
* ...
* };
*/

/**
* @param {function} isBadVersion()
* @return {function}
*/

var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
let left=1,right=n;
while(left<right){
const mid=left+Math.floor((right-left)/2)
if(isBadVersion(mid)){
right=mid
}else{
left=mid+1
}
}
return left
}};



Comments

Post a Comment

Popular posts from this blog

LeetCode 350: Intersection of Two Arrays II

-
Question:-  Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order. Example 1: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted. Example 2: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Solution:- class Solution {     public int [] intersect ( int [] nums1 , int [] nums2 ) {         int length1 = nums1 . length ;           int length2 = nums2 . length ;         int [] ans = new int [ length1 * length2 ];         int i = 0 , j = 0 , k = 0 ;         Arrays . sort ( nums1 );         Arrays . sort ( nums2 );         while ( i < length1 && j < length2 ){             if ( nums1 [ i ...
Read more

LeetCode 35: Search Insert Position

-
 Question Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with  O(log n)  runtime complexity.   Example 1: Input: nums = [1,3,5,6], target = 5 Output: 2 Example 2: Input: nums = [1,3,5,6], target = 2 Output: 1 Example 3: Input: nums = [1,3,5,6], target = 7 Output: 4   Solution 1- Javascript /** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function ( nums , target ) { let left = 0 ; let right = nums . length ; while ( left < right ) { const middle = Math . floor (( left + right ) / 2 ); if ( nums [ middle ] < target ) { left = middle + 1 ; } else { right = middle ; } } return left ; };
Read more

LeetCode 217: Contains Duplicate

-
  Question Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true Solutions 1) Go func containsDuplicate ( nums [] int ) bool {     dict := make ( map [ int ] int )     for _ , num := range nums {         dict [ num ]= dict [ num ]+ 1         if ( dict [ num ]> 1 ){             return true ;         }             }     return false } 2) Javascript function containsDuplicate ( nums ) {   const temp = new Set ( nums );   return !( nums . length === temp . size ); }
Read more