{"id":1991,"date":"2024-03-01T12:00:00","date_gmt":"2024-03-01T12:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1991"},"modified":"2024-03-02T10:18:26","modified_gmt":"2024-03-02T10:18:26","slug":"first-bad-version-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/first-bad-version-problem\/","title":{"rendered":"First Bad Version Problem (C++, Java, Python)"},"content":{"rendered":"\n<p>Binary Search is one of the important topics that are asked in interviews. The basic idea is to check the middle value, and you decide to go either right or left based on this. The binary search helps you to reduce your time complexity significantly. This article will discuss the problem \u201cFirst Bad Version\u201d based on Binary Tree, which is also part of leetcode.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>First Bad Version Problem Explained<\/strong><\/h2>\n\n\n\n<p><strong>In the First Bad Version problem, you are given a number that represents the total number of versions of a product. Unfortunately, your latest version has some defects, causing all subsequent versions to be defective. Your task is to find the first defective version. You are provided with an API, bool isBadVersion(n), which indicates whether a given version is defective or not. Find the first defective version using the provided API while minimizing the number of calls made to it.<\/strong><\/p>\n\n\n\n<p>Here is how it works:<\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color wp-elements-aeb4aadf0667f828c0c261c34a6a6ae2\" style=\"background-color:#fedcba\"><code><strong>Input:<\/strong> n = 5, bad = 3.\n\n<strong>Output:<\/strong> t=2 -&gt;good\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t=3 -&gt;bad\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t=4 -&gt;bad\n\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t=5 -&gt;good.<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/0AIk7UevZ22_Psx-GIGIJ8Ni6chuW9ScncsJoiLcLsNDssGofcdn_t5Bk_bhziBy437UjpVK4hAea3IDaHMrkpl6yrnrpT1uWqujxuEuGcJrGJ1LEvtaHgvxwM5E-PPfHqXYfMDHNjy8TYtrVFI2z0k\" alt=\"Example of First Bad Version\"\/><\/figure>\n\n\n\n<p>The basic approach to the given problem is to start from the first index and call the API for each of them till it returns that the given version is bad. Return this as the first bad version.<\/p>\n\n\n\n<p>Let\u2019s understand this approach step by step:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Start from index 1 and call the API isBadVersion.<\/li>\n\n\n\n<li>If you get true as a result return this index as the first Badversion<\/li>\n\n\n\n<li>Otherwise, move to the next index and repeat the same process till you reach the bad version.<\/li>\n<\/ul>\n\n\n\n<p>The time complexity for the above approach is O(n) where n is the total number of versions given to you as we are going to each index and at worst the bad version may be the last so the worst time complexity is O(n). The space complexity is O(1) as we are not using any extra space.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Binary Search Approach<\/strong><\/h2>\n\n\n\n<p>In the above approach, it took O(n) time, which can be reduced if we use <a href=\"https:\/\/favtutor.com\/blogs\/searching-algorithms\">binary search<\/a>. As we know, all the versions after the first bad version are bad. Therefore, if we find any bad version, the first bad version is either at this index or before it, but not after. Similarly, if we determine that this index is not a bad one, we need to search after it, not before it. Let&#8217;s examine this approach:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/neon7egNCPGNNnVNa-Yhblk_MfEzXZRVz2a2-VI8yhPYsY5nwoBEFbb-dFIPcy-5sYDftRR0CLhs-17zzCRluqXu6v2n_GHSyJOwivYZnp-Vj2A0X4cTc-wd1q--8eZVKOZypffLeIL9Q8OrPlcXbsQ\" alt=\"Example array.\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Create two variables, first and last which store the starting and ending index respectively.<\/li>\n\n\n\n<li>Now keep on iterating till the first index is less than the last index.<\/li>\n\n\n\n<li>Check if the middle element of the first and last index is bad or not with the help of API.<\/li>\n\n\n\n<li>If it is the bad version update the last index to the middle index.<\/li>\n\n\n\n<li>If not, update the first index to the mid+1 index.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/flwETS7H2ybq-aHhlPSCHrj-DG_Hg0NUjdzTESV9p5prghyvL0Eixuj9M2WviVYU7a2PRr7zS2FL40ArdZXCC_Ni-I-JO7TeCaWaoThdAiQTcOIl2I7m_GiQ3RUKbOdKhAxoHLqQdxDFOXdIDTOq1ps\" alt=\"Binary Search implementation.\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If at any point the first and last index become equal return the first index as the first bad version as an answer.<\/li>\n<\/ul>\n\n\n\n<p>Let\u2019s examine the code for the above process.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ implementation of the Binary Search approach:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">class Solution {\n\npublic:\n\n\u00a0\u00a0\u00a0\u00a0int firstBadVersion(int n) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ binary search approach\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ first represents the starting index and last represents the last index.\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0long long int first = 1, last = n;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while(first&lt;last){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0long long int mid = (first+last)\/2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ if isBadVersion return true at mid means the mid value is bad =&gt; all the values after that are also bad.\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(isBadVersion(mid)) last = mid;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else first = mid+1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return first;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n};<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>You can program it with Java also:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">public class Solution {\n\n\u00a0\u00a0\u00a0\u00a0public int firstBadVersion(int n) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ Binary search approach\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ First represents the starting index and last represents the last index.\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0long first = 1, last = n;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while (first &lt; last) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0long mid = (first + last) \/ 2;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ If isBadVersion returns true at mid means the mid value is bad =&gt; all the values after that are also bad.\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (isBadVersion(mid)) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0last = mid;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0} else {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0first = mid + 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return (int) first;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>We can do this in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">class Solution:\n\n\u00a0\u00a0\u00a0\u00a0def firstBadVersion(self, n: int) -&gt; int:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0# Binary search approach\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0# First represents the starting index and last represent the last index.\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0first = 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0last = n\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0while first &lt; last:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0mid = (first + last) \/\/ 2\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0# If isBadVersion returns true at mid means the mid value is bad =&gt; all the values after that are also bad.\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if self.isBadVersion(mid):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0last = mid\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0first = mid + 1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return first<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Complexity Analysis<\/strong><\/h3>\n\n\n\n<p>The time complexity for solving the First Bad Version problem is reduced to O(log(n)) due to binary search. As we are just iterating loops for at most log(n) times. The space complexity will again be 0.<\/p>\n\n\n\n<p>Here is the comparison of both methods:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter\"><table><thead><tr><th class=\"has-text-align-center\" data-align=\"center\"><strong>     Approach<\/strong><\/th><th><strong>Time Complexity<\/strong><\/th><th><strong> Space Complexity<\/strong><\/th><th><strong>Description<\/strong><\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-center\" data-align=\"center\">&nbsp; &nbsp; Brute Force<\/td><td>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; O(n)<\/td><td>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; O(1)<\/td><td>We are iterating loop for at most n times where n is the total number of versions of a product.<\/td><\/tr><tr><td class=\"has-text-align-center\" data-align=\"center\">&nbsp;Optimized  Approach<\/td><td>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; O(log(n))<\/td><td>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; O(1)<\/td><td>We are using binary search for this which reduced our time complexity to O(log(n)).<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In this article, we have seen how we can use binary search to solve the <a href=\"https:\/\/leetcode.com\/problems\/first-bad-version\/description\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> of the First Bad Version. This helps us reduce our time complexity from O(n) to O(log(n)). Binary search has many more applications.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Find out how to solve the popular leetcode problem called First Bad Version using Binary Search with implementation in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":2019,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[31,14,33,15,32],"class_list":["post-1991","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-c","tag-dsa","tag-java","tag-leetcode","tag-python"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1991","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1991"}],"version-history":[{"count":7,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1991\/revisions"}],"predecessor-version":[{"id":2122,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1991\/revisions\/2122"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2019"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1991"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1991"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1991"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}