educative.io

Number of API calls is one less than expected for certain cases

Courses
, ,
#1

Following is my solution for the problem statement first bad version.
For my solution, firstBadVersion is always correct (Checked using LeetCode #278).

However, it reports (expectedCount - 1) API calls for certain test cases.
Need help with it.

public class FBVersion{
   
// -- DO NOT CHANGE THIS SECTION -----------------
   public static boolean isBadVersion(int v){ // isBadVersion() is the API function that returns true or false depending upon whether the provided version ID is bad or not
      return Main.isBad(v);
   }
//-------------------------------------------------

   public static int[] firstBadVersion(int n) {
      int left = 1;
      int right = n;
      int nCalls = 1;

      while(left <= right) {
         int mid = (int) Math.floor((left+right)/2);
         boolean isBad = isBadVersion(mid);
         if(!isBad) {
            left = mid + 1;
         }
         else if(isBad && isBadVersion(mid - 1)){
            right = mid - 1;
         }
         else {
            return new int[]{mid, nCalls};
         }
         nCalls++;
      }

      
      return new int[]{0, 0};
   }
}
1 Like
#2

Hello @Harsh_Balyan,

Thank you for your feedback on this lesson. I noticed a few spots where we can optimize your code to meet the expected performance:

  1. API Call Counter: Start nCalls at 0 and increment it strictly when isBadVersion is called. This ensures we track the number of API calls precisely.
  2. Loop Optimization: Change your loop to while (left < right). This minor tweak helps zero in on the first bad version more efficiently by avoiding unnecessary checks.
  3. Counter Increment: Make sure to increment nCalls only at the point of making an API call. Any additional increments could misrepresent the actual API calls made.

The logic used to return the first bad version upon finding a bad version that does not have a bad predecessor (else { return new int[]{mid, nCalls}; } ) is sound in principle. However, this approach has a flaw in its execution. If the first bad version is at the start of the array (i.e., version 1 is bad), the condition else if(isBad && isBadVersion(mid - 1)) will never be true for the first version, because there’s no mid - 1 to check, leading to potentially incorrect behavior if not handled correctly outside this snippet’s context.

Implementing these changes will refine your solution, ensuring it efficiently identifies the first bad version with the least number of API calls.

Here’s the updated code:

   public static int[] firstBadVersion(int n) {
      int left = 1;
      int right = n;
      int nCalls = 0; // Correctly count API calls from 0

      while (left < right) {
         int mid = left + (right - left) / 2;
         if (isBadVersion(mid)) {
               right = mid; // Mid might be the first bad version, so we keep it in the search space
         } else {
               left = mid + 1; // First bad version must be after mid
         }
         nCalls++; // Count each call to isBadVersion correctly
      }

      // When left == right, we've found the first bad version
      // No need to increment nCalls after finding the first bad version
      return new int[]{left, nCalls};
   }

For your reference, we are actively working on improving the quality of this lesson to make it more understandable. Feel free to share more suggestions and feedback. We’d be happy to help. Thanks!

Happy learning!