Problem 278

Abstract / Summary

You must find the earliest broken version in a sequence of versions where all before it are fine.

Note

The full problem description, including helpful examples, can be found on LeetCode.

C++ 0278.cpp

class Solution {
public:
    int firstBadVersion(int n) {
        int64_t N = int64_t(n) + 1; // one-based

        int64_t step  = 1;
        while (step*2 < N)
            step *= 2;

        int64_t guess = N / 2;
        while (true)
        {
            step >>= 1;

            bool isBad = isBadVersion(guess-1); // zero-based
            if (isBad)
                guess -= step;
            else
                guess += step;

            if (step == 0)
            {
                if (isBad)
                    return guess-1;
                else
                    return guess;
            }
        }

        return guess;
    }
};
32 lines | 685 bytes | submitted August 7, 2023 | GitHub   7% comment ratio | tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 47% (4+ million submissions).

Typical patterns to solve this problem:
  • Binary Search
  • Interactive
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The function firstBadVersion determines the earliest version that is marked as bad among a sequence of versions numbered from 0 to n-1. It treats the version indices as zero-based for the external API isBadVersion but internally works with a one-based representation to simplify the binary search logic. The algorithm builds an initial step size that is the largest power of two not exceeding the range, then iteratively refines a guess by halving the step and moving the guess left or right depending on the result of isBadVersion. The loop terminates when the step size reaches zero, at which point the exact boundary between good and bad versions is known and the appropriate index is returned.

Key Steps

The first important operation converts the input size to a one-based range:

int64_t N = int64_t(n) + 1; // one-based

Using a 64-bit integer prevents overflow when n is close to the maximum value of a 32-bit signed integer.

Next, the algorithm finds the greatest power of two that is still smaller than N. This value becomes the initial step size:

int64_t step  = 1;
while (step*2 < N)
    step *= 2;

With the step prepared, the initial guess is placed at the midpoint of the one-based interval:

int64_t guess = N / 2;

The core of the method is an infinite loop that repeatedly halves the step and adjusts the guess:

while (true)
{
    step >>= 1;                     // halve the step

    bool isBad = isBadVersion(guess-1); // query using zero-based index
    if (isBad)
        guess -= step;              // move left if current guess is bad
    else
        guess += step;              // move right otherwise

    if (step == 0)
    {
        if (isBad)
            return guess-1;         // the bad version is just left of guess
        else
            return guess;           // guess itself is the first good version
    }
}

The loop ends only when step becomes zero, guaranteeing that the search space has been narrowed to a single candidate.

Edge Cases

The implementation gracefully handles the situation where the very first version (index 0) is already bad. In that case, the initial guess may be greater than zero, but the binary refinement will eventually move the guess left until step reaches zero and isBad remains true, causing the function to return guess-1, which evaluates to 0.

When no version is bad (i.e., all calls to isBadVersion return false), the algorithm will keep moving the guess rightward. Once step collapses to zero, isBad is false and the function returns guess, which will be equal to N-1 in the one-based system, corresponding to the last zero-based index n-1. This correctly indicates that there is no bad version within the supplied range.

If n equals 0, the conversion to one-based yields N = 1. The step-building loop never executes because step*2 (2) is not less than N. The initial guess becomes 0, and the subsequent loop immediately reduces step to zero, returning guess (0). This behavior aligns with the expectation that an empty range yields a result of 0, which can be interpreted as “no bad version”.

Performance Optimizations

The algorithm avoids the classic recursive binary search by using an iterative approach with explicit step manipulation. By pre-computing the largest power of two less than the range, it ensures that the first iteration starts with the maximum possible jump, reducing the number of API calls needed to locate the boundary.

The use of bitwise right-shift (step >>= 1) to halve the step size is a low-cost operation compared to arithmetic division. Maintaining the step as a power of two throughout the search guarantees that each iteration reduces the search interval by exactly half, leading to a predictable convergence pattern.

All arithmetic is performed with 64-bit integers, eliminating the risk of overflow that could otherwise cause additional conditional checks or corrective logic. This choice streamlines the loop body and keeps the number of executed instructions minimal.

By keeping the loop condition while (true) and breaking only when step reaches zero, the code eliminates the need for extra state variables or complex loop predicates, which contributes to tighter CPU pipelines and better branch prediction in typical execution environments.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a long line of blocks and some of them are broken. You need to find the very first block that is broken without checking every single one of them because that would take way too long. To do this, you move to the middle of the line and ask if that block is broken.

If the middle block is broken, you know the first broken one must be at that spot or somewhere behind it, so you move your attention to the middle of that side. If the block is working perfectly, you know the first broken one must be somewhere further ahead, so you shift your search to the middle of the remaining part. You keep splitting the section in half over and over again like a smart game of hide and seek until you are standing right in front of the very first broken block. By jumping around like this instead of looking at every block, you save a lot of time and find the answer much faster.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 5 | μ = 4.89 | σ = 1.83

Complexity Analysis

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Java Python TS
WalkCCC C++ Java Python
leetcode.ca C++ Java Python JS Go Rust TS
LeetcodeHelp C++ Java Python
MemoryLimitExceeded C++ Python
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
Dijkstra-Edu Java
DimitrisJim C
everthis JS
fartem Ruby
fengvyi C++
fpdjsns C++
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lennylxx C
linouk23 C++
lkwq007 Python
pruthvikp Python
qiyuangong Python
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
chandansgowda Python
charles-wangkai Java
chenyanzhe C++
Dijkstra-Edu Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fengvyi C++
fpdjsns C++
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lennylxx C
linouk23 C++
lkwq007 Python
pruthvikp Python
qiyuangong Python
shreymehul C#
sonugiri1043 C++
suxrobGM C#
varunu28 Java
vli02 C
vthwang Java
XiaotaoGuo C++
yuanliu666 Kotlin
52 links | 36 authors | 11 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'First Bad Version - Leetcode 278 - Binary Search (Python)'
Greg Hogg 9 mins
First Bad Version - Leetcode 278 - Binary Search (Python)
YouTube video 'First Bad Version | Leetcode 278 Solution | Searching and Sorting'
Pepcoding 10 mins
First Bad Version | Leetcode 278 Solution | Searching and Sorting
YouTube video 'First Bad Version | LeetCode 278 (C++, Java, Python) | May LeetCoding Day 1'
Knowledge Center 13 mins
First Bad Version | LeetCode 278 (C++, Java, Python) | May LeetCoding Day 1
YouTube video 'LeetCode 278. First Bad Version - Interview Prep Ep 74'
Fisher Coder 8 mins
LeetCode 278. First Bad Version - Interview Prep Ep 74
YouTube video 'First Bad Version -  LeetCode 278 - Coding Interview Questions'
One Code Man 5 mins
First Bad Version - LeetCode 278 - Coding Interview Questions
YouTube video 'FIRST BAD VERSION | LEETCODE 278 | PYTHON BINARY SEARCH SOLUTION'
Cracking FAANG 9 mins
FIRST BAD VERSION | LEETCODE 278 | PYTHON BINARY SEARCH SOLUTION
YouTube video '#1 Overflow Bug in Binary Search Algorithm | First bad version Leetcode'
IT Freak 12 mins
#1 Overflow Bug in Binary Search Algorithm | First bad version Leetcode
YouTube video '278  First Bad Version | Zero to FAANG | Searching in Arrays | Leetcode'
Programmers Zone 18 mins
278 First Bad Version | Zero to FAANG | Searching in Arrays | Leetcode
YouTube video 'First Bad Version #leetcode #binarysearch'
Deepti Talesra 6 mins
First Bad Version #leetcode #binarysearch
YouTube video 'First Bad Version LeetCode | LeetCode 278 | Binary Search'
Naresh Gupta 5 mins
First Bad Version LeetCode | LeetCode 278 | Binary Search
YouTube video 'LeetCode 278. First Bad Version Explanation and Java Solution'
happygirlzt 5 mins
LeetCode 278. First Bad Version Explanation and Java Solution
YouTube video 'LeetCode 278. First Bad Version 中文解释 Chinese Version'
happygirlzt 4 mins
LeetCode 278. First Bad Version 中文解释 Chinese Version
YouTube video 'Leetcode 278: First Bad Version | Binary Search & Brute Force in Telugu | srkcodes'
Srk Codes 6 mins
Leetcode 278: First Bad Version | Binary Search & Brute Force in Telugu | srkcodes
YouTube video 'LeetCode 278. First Bad Version - Binary Search - JavaScript - Leetcode75'
LeetCodeWithMonu 6 mins
LeetCode 278. First Bad Version - Binary Search - JavaScript - Leetcode75
YouTube video 'Leetcode 278 - First Bad Version (JAVA, Solution Explain!)'
LC Bear 6 mins
Leetcode 278 - First Bad Version (JAVA, Solution Explain!)
YouTube video 'First Bad Version - Google Interview Questions - LeetCode 278 Solution - C++'
nexTRIE 8 mins
First Bad Version - Google Interview Questions - LeetCode 278 Solution - C++
YouTube video 'First Bad Version || May LeetCoding Challenge || [ C++ SOLUTION ]'
code Explainer 8 mins
First Bad Version || May LeetCoding Challenge || [ C++ SOLUTION ]
YouTube video 'Leetcode | 278. First Bad Version | Easy |  Approach: Binary Search | Javascript'
Software Interviews Prep 13 mins
Leetcode | 278. First Bad Version | Easy | Approach: Binary Search | Javascript
YouTube video '278. First Bad Version | Leetcode | Python'
Abdullah Arshed 7 mins
278. First Bad Version | Leetcode | Python
YouTube video 'Facebook Coding Interview Question | Leetcode 278 | First Bad Version'
WorkWithGoogler 7 mins
Facebook Coding Interview Question | Leetcode 278 | First Bad Version
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

39 easy 31 medium 1 hard
72 solutions   August 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality