Skip to main content

278. First Bad Version

easyAsked at Intel

You have n versions [1..n] and an isBadVersion(i) API. Find the first bad one with the fewest API calls. Intel asks because this is binary search wearing a pragmatic disguise — same algorithm as LC 704, but the cost model is API-call count, which mirrors real systems work like git bisect.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE phone-screen reports cite first-bad-version as a recurring binary-search variant.
  • GeeksforGeeks (2025-09)— Intel Interview Experience archives reference it under 'binary search applications'.
  • LeetCode discuss (2025-10)— Intel-tagged in the LC company-frequency listing.

Problem

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.

Constraints

  • 1 <= bad <= n <= 2^31 - 1

Examples

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

Approaches

1. Linear scan (brute)

Call isBadVersion(i) for i = 1, 2, 3... and return the first true.

Time
O(n) API calls
Space
O(1)
function solutionLinear(isBadVersion) {
  return function(n) {
    for (let i = 1; i <= n; i++) {
      if (isBadVersion(i)) return i;
    }
    return -1;
  };
}

Tradeoff: O(n) API calls — exactly what the problem statement asks us to minimize. Wrong answer.

2. Binary search (optimal)

Search for the first index where isBadVersion flips from false to true. Lo=1, hi=n. Mid: if bad, shrink right; if good, shrink left of mid+1.

Time
O(log n) API calls
Space
O(1)
function solution(isBadVersion) {
  return function(n) {
    let lo = 1, hi = n;
    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (isBadVersion(mid)) {
        hi = mid; // mid might be the answer; keep it
      } else {
        lo = mid + 1;
      }
    }
    return lo;
  };
}

Tradeoff: log2(2^31) ~= 31 API calls max. Note the asymmetric update — `hi = mid` not `hi = mid - 1` because mid itself might be the answer when it's bad. The loop terminates when lo === hi, which is necessarily the first bad version.

Intel-specific tips

Intel reviewers want you to use `lo + (hi - lo) / 2` (overflow-safe) since n can be 2^31 - 1. In C/C++ with int, `(lo + hi) / 2` overflows at n ~= 2^30. Also state out loud: 'I'm searching for the LEFT BOUNDARY of true values, so I use `hi = mid` instead of `hi = mid - 1`.' That distinction is the senior signal — there are two binary-search flavors (find-an-element vs find-a-boundary) and the boundary version is subtler.

Common mistakes

  • Updating hi to mid - 1 when isBadVersion(mid) is true — discards the true mid which might be the first bad version.
  • Looping with `while (lo <= hi)` and returning lo at the end — with asymmetric updates, this can over-advance. The clean version uses `lo < hi` and trusts the invariant.
  • Using `(lo + hi) / 2` with n = INT_MAX — overflow in C/C++.
  • Forgetting to start at version 1 (the problem is 1-indexed).

Follow-up questions

An interviewer at Intel may pivot to one of these next:

  • Search Insert Position (LC 35) — left-boundary binary search on a sorted array.
  • Find First and Last Position (LC 34) — two boundary searches.
  • What if the API costs $0.01 per call and you have 1000 versions? (Same algorithm, log2 (1000) ~= 10 calls = $0.10.)
  • What if the bad-version predicate isn't monotone? (Binary search no longer applies; you need a full linear scan or domain-specific bisection.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why `hi = mid` instead of `hi = mid - 1`?

We're searching for the first index where the predicate is true. If mid is bad (true), mid itself might be that first index — we can't exclude it. So we narrow to [lo, mid]. The strict `lo < hi` loop condition guarantees termination because hi - lo decreases by at least 1 each iteration.

How does this relate to git bisect?

Git bisect IS first-bad-version: given a sequence of commits where 'bad' starts at some point, find the first bad commit with log2(n) check-out-and-test calls. Same algorithm, exact same termination condition.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill First Bad Version and other Intel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →