Digit-by-digit arithmetic

39 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Reverse the number 123 to get 321. On paper you would write the digits down and read them backwards. A computer does not hold a number as digits; it holds a single value, so "read the digits backwards" has to be built from arithmetic. The two operations that expose digits are remainder and integer division: 123 mod 10 is 3, the last digit, and 123 divided by 10 with the fraction thrown away is 12, the number with that digit removed.

The by-hand alternative is converting to a string, reversing it, and converting back. That works, but it allocates memory, it hides what is happening, and interviewers want to see that you can handle overflow and signs, which strings do not help with.

Build the structure, one piece at a time

There are two variables. x is the number still to be read, and rev is the number built so far. Each step peels the last digit off x and pushes it onto the right end of rev; pushing a digit onto the right end means multiplying by 10 and adding:

When x becomes 0 there is nothing left to read and rev is the answer. Every digit problem is a variation on this loop. Adding digits (Add Digits) replaces "rev · 10 + digit" with "sum + digit". Checking a palindrome reverses only half the digits and compares the halves. Plus One walks from the right, adding and carrying. Square root by hand is the same idea with the decimal places found one at a time, though binary search is the usual code.

The one new piece is the overflow guard. If the answer must fit in a 32-bit signed integer, the largest value is 2,147,483,647. Before computing rev · 10 + digit, check that rev is below 214,748,364, or equal to it with the digit at most 7; otherwise the next step would exceed the limit and you must return 0.

Why it is correct

The invariant is that rev holds, in reverse, exactly the digits that have been removed from x. Write the original number as d_k … d₂ d₁. Before any step rev is 0 and nothing has been removed, so the claim holds trivially. Each step removes d_i, the current last digit, and appends it to rev. Appending a digit on the right of a decimal number is exactly rev · 10 + digit, because the old digits all move one place left. So after the step rev reads the removed digits in the order they were removed, which is right to left. When x is 0 all digits have been removed and rev reads all of them backwards.

Negative numbers need one decision: strip the sign, run the loop, put the sign back. In most languages the remainder of a negative number is negative, which would quietly break the loop.

Why it is fast

Each step removes one decimal digit, and a number x has ⌊log₁₀ x⌋ + 1 digits, so the loop runs that many times: 10 steps for a 10-digit number. That is O(log x) time, with two integer variables of memory. The string approach is also linear in the digit count but costs an allocation and gives you no overflow check for free.

How to recognise it in an interview

Cues: "digits", "reverse", "palindrome number", "sum of digits", "add one to the number represented by", "without converting to a string", and any mention of 32-bit overflow. Say: "I will peel digits with mod 10 and integer division by 10, and check overflow before each multiply".

Reverse Integer is the loop above with the guard. Palindrome Number reverses the number (or just its lower half) and compares; negative numbers are never palindromes. Plus One is the carry version: add 1 to the last digit, and while a digit became 10 set it to 0 and carry into the next one, remembering to grow the array when the carry falls off the front.

02The idea in one line

Peel digits with % 10 and / 10; rebuild with ×10, guard overflow.

Reach for it when: Reverse integer, palindrome number, plus one, add digits, sqrt, nth digit.

Cost: O(digits) time.

03The walk-through, step by step

The video works one example: Reverse Integer 123 → 321. These are its captions in order, so you can follow without the video or check a step you missed.

1. Peel the last digit with % 10, drop it with // 10
2. x % 10 = 3: the last digit of 123
3. rev = 0 + 3 = 3, x becomes 12
4. x % 10 = 2: the last digit of 12
5. rev = 30 + 2 = 32, x becomes 1
6. x % 10 = 1: the last digit of 1
7. rev = 320 + 1 = 321, x becomes 0
8. x is 0: stop. rev = 321
9. Guard overflow before each rev × 10 + digit step
10. One step per digit: O(log₁₀ x) time, O(1) space

04Asked at Google

10 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Math: Fast exponentiation, GCD and number theory, Random pick and reservoir sampling, Coordinate geometry with hashing.