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;
}
};
Difficulty
and has an acceptance rate of about 47% (4+ million submissions).
Typical patterns to solve this problem:
- Binary Search
- Interactive
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 34: Find First and Last Position of Element in Sorted Array
- problem 35: Search Insert Position
- problem 374: Guess Number Higher or Lower
Solved On The Same Day
- problem 13: Roman to Integer
- problem 21: Merge Two Sorted Lists
- problem 28: Find the Index of the First Occurrence in a String
- problem 35: Search Insert Position
- problem 58: Length of Last Word
- problem 66: Plus One
- problem 67: Add Binary
- problem 69: Sqrt(x)
- problem 70: Climbing Stairs
- problem 206: Reverse Linked List
- problem 242: Valid Anagram
- problem 283: Move Zeroes
- problem 367: Valid Perfect Square
- problem 374: Guess Number Higher or Lower
- problem 389: Find the Difference
- problem 441: Arranging Coins
- problem 459: Repeated Substring Pattern
- problem 509: Fibonacci Number
- problem 657: Robot Return to Origin
- problem 682: Baseball Game
- problem 704: Binary Search
- problem 709: To Lower Case
- problem 744: Find Smallest Letter Greater Than Target
- problem 746: Min Cost Climbing Stairs
- problem 860: Lemonade Change
- problem 896: Monotonic Array
- problem 976: Largest Perimeter Triangle
- problem 1137: N-th Tribonacci Number
- problem 1232: Check If It Is a Straight Line
- problem 1275: Find Winner on a Tic Tac Toe Game
- problem 1351: Count Negative Numbers in a Sorted Matrix
- problem 1491: Average Salary Excluding the Minimum and Maximum Salary
- problem 1502: Can Make Arithmetic Progression From Sequence
- problem 1523: Count Odd Numbers in an Interval Range
- problem 1539: Kth Missing Positive Number
- problem 1572: Matrix Diagonal Sum
- problem 1672: Richest Customer Wealth
- problem 1768: Merge Strings Alternately
- problem 1822: Sign of the Product of an Array
- problem 2: Add Two Numbers
- problem 5: Longest Palindromic Substring
- problem 33: Search in Rotated Sorted Array
- problem 34: Find First and Last Position of Element in Sorted Array
- problem 43: Multiply Strings
- problem 50: Pow(x, n)
- problem 54: Spiral Matrix
- problem 62: Unique Paths
- problem 63: Unique Paths II
- problem 64: Minimum Path Sum
- problem 73: Set Matrix Zeroes
- problem 74: Search a 2D Matrix
- problem 120: Triangle
- problem 139: Word Break
- problem 153: Find Minimum in Rotated Sorted Array
- problem 198: House Robber
- problem 221: Maximal Square
- problem 275: H-Index II
- problem 279: Perfect Squares
- problem 300: Longest Increasing Subsequence
- problem 436: Find Right Interval
- problem 445: Add Two Numbers II
- problem 528: Random Pick with Weight
- problem 540: Single Element in a Sorted Array
- problem 611: Valid Triangle Number
- problem 658: Find K Closest Elements
- problem 852: Peak Index in a Mountain Array
- problem 981: Time Based Key-Value Store
- problem 1041: Robot Bounded In Circle
- problem 1146: Snapshot Array
- problem 2300: Successful Pairs of Spells and Potions
- problem 154: Find Minimum in Rotated Sorted Array II
Extra
- 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