STEP 5 · STRINGS · PREDICT THE OVERFLOW · MEDIUM

String to Integer (atoi)

WHAT IT SAYS

Parse a leading integer out of a string: skip whitespace, take an optional sign, read digits until a non-digit, and clamp to the 32-bit range.

WHAT IT'S REALLY ASKING

"There is no algorithm here, there is a contract — and exactly one genuinely hard question buried inside it. You are about to compute res * 10 + digit, and you must know whether that will blow past the ceiling. But you cannot compute it to find out, because computing it is the thing that destroys the evidence. So how do you ask a question about a number you are not allowed to produce?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Accumulate, then look at the damage

O(n) time, O(1) space, and wrong

Run res = res * 10 + digit in a 32-bit int and watch for something suspicious — a value that suddenly went negative, or shrank when it should have grown — then clamp.

WHERE THE WORK IS WASTED — You are asking a corrupted value what it used to be. Signed overflow is undefined behaviour in C and C++ (the compiler is entitled to assume it never happens and optimise your check away), and even where it wraps predictably, the wreckage lies: 2147483647 * 10 + 7 can land back inside the positive range looking perfectly innocent. The information you needed — is this about to overflow? — existed BEFORE the multiplication, and you destroyed it by multiplying first. The redundancy is not wasted cycles; it is a check placed after the crime.

Parse into a wider type

O(n) time, O(1) space

Accumulate into a 64-bit long, compare against the 32-bit limits at the end, and clamp. Correct, and two lines shorter.

WHERE THE WORK IS WASTED — It works, but it does not solve the problem — it delegates it to a type that happens to be bigger. The moment the target IS your widest type (parse a 64-bit integer, and there is no 128), the trick evaporates and you are back where you started with nothing learned.

KEY OBSERVATION — THE UNLOCKlink

Predict the overflow with division; never detect it with wreckage.

Overflow is a property of the OPERANDS, not of the result. So ask the question of the operands, while they are all still intact. You want to know whether res * 10 + d will exceed INT_MAX. Over the real numbers, where nothing wraps, that inequality is equivalent to: res > (INT_MAX - d) / 10 Now audit every term in that rearranged inequality. res fits in an int (it did last iteration, and you checked). d is between 0 and 9. INT_MAX is by definition the largest int. Subtraction makes it smaller, division makes it smaller still. Nothing on either side of that comparison can overflow — it is arithmetic that is safe by construction, asking about arithmetic that is not. And it simplifies. INT_MAX is 2147483647, so INT_MAX / 10 is 214748364. If res is already greater than that, then res * 10 alone is over the line, no matter what digit arrives — clamp immediately. If res equals it exactly, you are balanced on the edge and the answer depends on d: the final digit of INT_MAX is 7, so d of 8 or more overflows. One asymmetry worth knowing, because it is where the last bug hides: the negative range is one wider than the positive one — INT_MIN is -2147483648, ending in 8, not 7. Two bounds, differing in the final digit. The professional move is to accumulate NEGATIVELY, which makes both signs share a single code path and a single clamp.

Four phases, one predictive check

O(n) time, O(1) space, one pass, no wider type required

Skip whitespace; consume at most one sign; then read digits, and BEFORE each multiply-and-add, test whether res exceeds INT_MAX/10, or equals it with an overflowing digit — if so, clamp to INT_MAX or INT_MIN and stop reading. The first non-digit ends the number. And read the rest of the specification like a contract: no digits at all means 0, a lone sign means 0, and clamping is not an error condition — it is the specified answer.

WHAT YOU TRADED — You give up the comfort of a bigger type and gain a routine that is correct in any fixed-width language, including one where you are already at the widest type available. The transferable lesson has nothing to do with strings: whenever an operation might leave the representable range, invert it — divide instead of multiply, subtract instead of add — so the danger condition is phrased entirely in values you already know are safe.

WATCH THE IDEA RUN

res 0

ceiling before x10 214748364

last digit allowed at the ceiling 7

clamped no

Whitespace skipped, no sign present. Now the only interesting part: every digit from here is a multiplication you are not allowed to get wrong.

step 1 / 11

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Ask Before You Commit

YOU'LL SEE IT AGAIN WHEN

An accumulation could exceed the type's range, and the obvious check inspects the result AFTER the very operation that would corrupt it.
The operation is invertible (multiply/divide, add/subtract), so the danger condition can be rewritten using only operands that are already known to be in range.
The problem is mostly a specification: the difficulty lives in enumerating states and edge cases, not in the complexity.

SAME BLUEPRINT, DIFFERENT PROBLEM

Reverse IntegerDivide Two Integers (without multiply or divide)Valid NumberAdd Binary

The bar isn't "solved it once." It's "could rebuild it from the observation."