Number math

Problem

These questions hand you a number, or a string of digits, and ask you to transform it: reverse it, test it for symmetry, convert it to or from another notation, add one, multiply two of them, or compute a power. The obvious answers either convert to a string and back (often banned, or hiding the point), loop n times when n is a billion, or quietly overflow a 32-bit integer that the problem says you must respect. The pattern is to treat a number as a sequence of digits in some base, process it from the cheap end (the last digit, the lowest bit), and keep every intermediate value inside its stated range.

Intuition

A number written in base ten is a list of digits wearing a disguise. x % 10 reads the last digit, x // 10 removes it, and r * 10 + d appends d to r. With those three moves you can pop digits off one number and push them onto another, which reverses it, and you never need a string. The only thing to watch is the size of what you are building: in Python integers never overflow, but the problems are set for languages where they do, and the interviewer wants to see you check the bound before the multiply that would break it.

Powers work the same way in base two. Thirteen is 1101 in binary, so x¹³ = x⁸ · x⁴ · x¹. The powers x, x², x⁴, x⁸ each come from squaring the one before, so you only need as many squarings as n has bits, and you multiply in the ones whose bit is set.

Read right to left: each box below is the square of the one to its right, and amber bits pick which squares go into the product. The diagram scrolls sideways on a narrow screen.

Mechanics

Peeling and building digits

Invariant for reversing: after k steps, result holds the last k digits of x in reverse order and rest holds the other digits in their original order. Each step moves one digit from the end of rest to the end of result, so after ⌊log₁₀ x⌋ + 1 steps (one per digit) rest is empty and result is the full reversal. Work on abs(x) and put the sign back at the end: Python's % and // round toward minus infinity, so -123 % 10 is 7, not −3, which is a classic surprise for people coming from C or Java.

Checking the bound before crossing it

If the answer must fit in [−2³¹, 2³¹ − 1], the step result * 10 + digit overflows exactly when result > INT_MAX // 10, or when result == INT_MAX // 10 and digit > INT_MAX % 10 (which is 7). Testing this before the multiply is what makes the check meaningful in a fixed-width language, where the overflowed value would already be garbage. The same check, with the negative bound's last digit 8, clamps atoi. Python will happily compute the big number, so on these problems you either check the bound explicitly or compare the final value against the range; the first is the answer an interviewer is looking for.

Reversing only half

Palindrome Number has a neater invariant: keep moving digits from rest to half while rest > half. When the loop stops, half has at least as many digits as rest, so it holds the back half reversed. The number is a palindrome when the halves are equal (even length) or equal after dropping the middle digit with half // 10 (odd length). Only half the digits are ever built, so no overflow is possible. Negative numbers and positive numbers ending in 0 are rejected up front: no palindrome starts with a minus sign or a leading zero.

Square-and-multiply

Write n in binary as a sum of distinct powers of two. Then xⁿ is the product of x^2k over the set bits k. The loop keeps power = x2k for the current bit and result = the product of the powers for the bits already read. Each iteration multiplies power into result if the bit is set, squares power, and shifts n right. That is at most 2 log₂ n multiplications. A negative n means 1 / x⁻ⁿ, so invert x first and use −n; in a fixed-width language take care that −(−2³¹) does not fit, which is why the exponent is widened before negating.

Multiplying digit strings

For digit strings a (length m) and b (length n), the product has at most m + n digits. Index the result slots 0 to m + n − 1 from the left. Digit a[i] stands for a[i] · 10^m−1−i and b[j] for b[j] · 10^n−1−j, so their product's units digit belongs at power m + n − 2 − i − j, which is slot i + j + 1, and its tens digit at slot i + j. Processing pairs from the right and adding into those two slots keeps every slot except the leftmost touched one below ten, and the last pair settles slot 0. Strip leading zeros at the end, keeping one zero if the product is zero.

Each row is the slot array after one digit product. Amber is where the product's units digit was added; blue is the slot that received the carry.

Other bases and notations

Converting to base b peels digits with divmod(n, b), most significant last, so reverse at the end. Excel column titles are base 26 with digits A–Z standing for 1–26 and no zero (bijective base 26), so subtract one before each divmod: then the remainder 0 to 25 maps onto A to Z, and Z (26) does not spill into a phantom zero digit. Roman numerals are additive with one rule: a symbol worth less than its right neighbour is subtracted. Greatest Common Divisor of Strings reduces to Euclid on the lengths once you check that the two strings commute, s + t == t + s, which holds exactly when both are repeats of one common block.

Worked example

Reverse Integer, x = −1230. Work on 1230; the bound for a negative result is 2147483648.

The trailing zero becomes a leading zero and disappears. Putting the sign back gives -321.

The overflow case, x = 1534236469. The reversal would be 9646324351, which is larger than 2147483647.

At the last step the result is 964632435, already above 214748364 = INT_MAX // 10, so multiplying by ten would overflow. The check fires first and the function returns 0.

Palindrome Number, x = 12321.

The loop stops when the rest (12) is no longer greater than the half (123). The length is odd, so drop the middle digit: 123 // 10 = 12, which matches, so 12321 is a palindrome. For 1221 the loop stops at rest 12 and half 12 after 2 steps.

Pow(x, n), x = 3, n = 13 (binary 1101).

6 multiplications give 3¹³ = 1594323. With a negative exponent the base is inverted first: 2⁻² runs the same loop on 0.5 and returns 0.25.

Multiply Strings, "123" × "45". The table repeats the diagram's slot array after each digit product.

Stripping the leading zero gives 5535.

Smaller conversions.

Implementation

INT_MAX, INT_MIN = 2**31 - 1, -2**31


def reverse(x):
    sign = -1 if x < 0 else 1
    limit = INT_MAX if sign > 0 else -INT_MIN
    rest, result = abs(x), 0
    while rest:
        rest, digit = divmod(rest, 10)
        if result > limit // 10 or (result == limit // 10 and digit > limit % 10):
            return 0                      # checked before the multiply that would overflow
        result = result * 10 + digit
    return sign * result


def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

Variations and edge cases

def is_palindrome(x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    half = 0
    while x > half:
        x, digit = divmod(x, 10)
        half = half * 10 + digit
    return x == half or x == half // 10


def multiply(a, b):
    slots = [0] * (len(a) + len(b))
    for i in range(len(a) - 1, -1, -1):
        for j in range(len(b) - 1, -1, -1):
            total = int(a[i]) * int(b[j]) + slots[i + j + 1]
            slots[i + j + 1] = total % 10
            slots[i + j] += total // 10
    return "".join(map(str, slots)).lstrip("0") or "0"


def column_title(n):
    letters = []
    while n:
        n, r = divmod(n - 1, 26)          # bijective base 26: digits are 1..26
        letters.append(chr(ord("A") + r))
    return "".join(reversed(letters))


def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

• Negative numbers in Python. -7 // 2 is −4 and -7 % 2 is 1. Work on abs(x), or use int(a / b) and math.fmod when you need truncation toward zero.
• The asymmetric range. −2³¹ fits but 2³¹ does not, so the positive and negative bounds have different last digits (7 and 8). Negating INT_MIN overflows in fixed-width languages.
• Zero. Reversing 0 and multiplying by "0" are the inputs where loops run zero times or strip every digit; return "0" rather than the empty string. A column title for 1 ("A") is the smallest input, with a single pass.
• Floating point. x ** 0.5 and math.log10 round; use math.isqrt and integer loops when exactness matters, and compare floats with a tolerance.
• Modular answers. When a problem says "return it modulo 10⁹ + 7", reduce after every addition and multiplication; Python's built-in pow(x, n, m) is square-and-multiply with a modulus.

Complexity and tradeoffs

• Digit loops (reverse, palindrome, digit sums, base conversion): O(log x) time, one step per digit, and O(1) space. Converting to a string is also O(log x) and is fine unless the problem forbids it.
• Pow: O(log n) multiplications against n − 1 for the naive loop, which times out at n = 2³¹. The recursive form, xⁿ = (x^n/2)², is the same algorithm with O(log n) stack.
• Multiply strings: O(m · n) time and O(m + n) space. Karatsuba's divide and conquer is O(n^1.585), which is what CPython uses for huge integers, and FFT-based methods (as in GMP) are near-linear for very large operands, but nobody expects them in an interview.
• gcd: O(log min(a, b)) steps; the worst case is consecutive Fibonacci numbers (Lamé's theorem).
• When it is the wrong tool. Adding numbers stored as linked lists is the same carry loop but belongs to linked lists. Counting lattice paths is a binomial coefficient, but grid DP is the safer derivation. Repeated digit-square sums that may loop forever, as in Happy Number, are a cycle question for fast and slow pointers.

Problems

Start with Palindrome Number and Plus One to get used to digits and carries, then Reverse Integer for the overflow check and Pow(x, n) for square-and-multiply. Multiply Strings is the one most people need to practise twice: derive the i + j + 1 slot rather than memorizing it.

Easy

• 9. Palindrome Number Grind 169
  Reverse only the lower half of the digits and compare it with the upper half, which avoids overflow and string conversion.
• 13. Roman to Integer Grind 169 NeetCode 250
  Scan symbol values left to right and subtract any value that is smaller than the one after it.
• 66. Plus One NeetCode 150 NeetCode 250
  Add one from the last digit and carry left; only an all-nines number grows by a new leading digit.
• 168. Excel Sheet Column Title NeetCode 250
  This is base 26 with no zero digit, so subtract one before each modulo and division.
• 1071. Greatest Common Divisor of Strings NeetCode 250
  A common divisor string exists only if s+t equals t+s, and then its length is the gcd of the two lengths.

Medium

• 7. Reverse Integer Grind 169 NeetCode 150 NeetCode 250
  Peel digits off with modulo and division, and check against the 32-bit bounds before each multiply-by-ten rather than after.
• 8. String to Integer (atoi) Grind 169
  Treat parsing as a tiny state machine: skip spaces, read one sign, consume digits, and clamp the moment the value would leave the 32-bit range.
• 43. Multiply Strings NeetCode 150 NeetCode 250
  Digit i of one number times digit j of the other contributes to position i+j+1 of the product, so accumulate and carry in an array.
• 50. Pow(x, n) Grind 169 NeetCode 150 NeetCode 250
  Square the base and halve the exponent at each step, handling a negative exponent by inverting the base first.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 67. Add Binary Easy
• 202. Happy Number Easy
• 268. Missing Number Easy
• 2. Add Two Numbers Medium
• 62. Unique Paths Medium
• 227. Basic Calculator II Medium
• 343. Integer Break Medium
• 877. Stone Game Medium
• 2807. Insert Greatest Common Divisors in Linked List Medium
• 224. Basic Calculator Hard
• 2709. Greatest Common Divisor Traversal Hard

Connections

Square-and-multiply first appeared on this site as a recursion example in recursion and the call stack; the loop here is the same algorithm read bit by bit. Bit manipulation picks up where this page stops, doing arithmetic on the base-two digits directly. Carry propagation reappears in Add Two Numbers, and the "check the bound before you cross it" habit matters again whenever an index or a sum could run past its range.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, section 31.2 (Euclid's algorithm and Lamé's theorem) and section 31.6 (modular exponentiation by repeated squaring).
• Knuth, D. E., The Art of Computer Programming, volume 2, Seminumerical Algorithms, section 4.3.1 (classical multiple-precision arithmetic) and section 4.6.3 (evaluation of powers).
• Skiena, S., The Algorithm Design Manual, the catalog's numerical problems: arbitrary-precision arithmetic and factoring.
• Sedgewick and Wayne, Algorithms, section 1.1, on Euclid's algorithm and integer types and their ranges.
• Karatsuba, A. and Ofman, Yu., "Multiplication of many-digital numbers by automatic computers", Doklady Akademii Nauk SSSR, 1962, the first sub-quadratic multiplication.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.