Big Integer Arithmetic on Strings

"Add/multiply two numbers given as strings, without converting them to integers" is a classic interview task. The solution is the arithmetic you learned in school: work digit by digit from the least significant end and propagate carries (or borrows). The same code handles linked-list digits, digit arrays and other bases.

Intuition

Store a number as its digits. Adding two numbers digit by digit produces at most a carry of 1 into the next position; subtracting may need a borrow of 1 from the next position. Multiplying digit i of a (counted from the right, starting at 0) by digit j of b contributes to position i + j of the product, so an n-digit times m-digit product fits in n + m digits, and all carries can be resolved in a single pass at the end. Dividing by a small number is long division from the most significant digit, carrying the remainder to the right.

Python's built-in integers are already arbitrary precision, which is exactly why interviews forbid int(a) + int(b): they want the carry logic. (Note that since Python 3.11, converting strings longer than about 4300 digits to int raises an error by default.)

When to use it in interviews / OAs

• Inputs are numeric strings or digit lists that may exceed 64 bits.
• "Add binary strings", "add two numbers stored in linked lists", "plus one on a digit array".
• Factorials or powers far beyond 64 bits in a language without big integers.
• A huge number given as a string, but you only need it modulo something (process digit by digit).

Template

def add_strings(a: str, b: str, base: int = 10) -> str:
    # schoolbook addition of two non-negative numbers written in `base` (2..10)
    i, j, carry = len(a) - 1, len(b) - 1, 0
    out = []
    while i >= 0 or j >= 0 or carry:
        total = carry
        if i >= 0:
            total += int(a[i])
            i -= 1
        if j >= 0:
            total += int(b[j])
            j -= 1
        carry, digit = divmod(total, base)
        out.append(str(digit))
    return "".join(reversed(out)) or "0"


def compare(a: str, b: str) -> int:
    # -1, 0 or 1 for non-negative numbers without leading zeros
    if len(a) != len(b):
        return -1 if len(a) < len(b) else 1
    return (a > b) - (a < b)  # same length: string order equals numeric order


def subtract_strings(a: str, b: str) -> str:
    # a - b for a >= b >= 0
    i, j, borrow = len(a) - 1, len(b) - 1, 0
    out = []
    while i >= 0:
        d = int(a[i]) - borrow - (int(b[j]) if j >= 0 else 0)
        borrow = 1 if d < 0 else 0
        out.append(str(d + 10 * borrow))
        i -= 1
        j -= 1
    return "".join(reversed(out)).lstrip("0") or "0"

For a - b with a < b, compute b - a and prepend a minus sign; compare tells you which case you are in.

def multiply_strings(a: str, b: str) -> str:
    # digit i of a times digit j of b (both from the right) lands at position i + j
    if a == "0" or b == "0":
        return "0"
    res = [0] * (len(a) + len(b))
    for i, x in enumerate(reversed(a)):
        for j, y in enumerate(reversed(b)):
            res[i + j] += int(x) * int(y)
    carry = 0
    for k in range(len(res)):  # resolve all carries in one pass
        carry, res[k] = divmod(res[k] + carry, 10)
    return "".join(map(str, reversed(res))).lstrip("0")


def divide_small(a: str, d: int) -> tuple[str, int]:
    # long division of a big number by an ordinary integer d > 0: (quotient, remainder)
    out, rem = [], 0
    for ch in a:
        rem = rem * 10 + int(ch)
        out.append(str(rem // d))
        rem %= d
    return "".join(out).lstrip("0") or "0", rem

Keeping only rem from divide_small is how you compute "a huge number modulo m" without ever building the number.

Same loop, other containers

The carry loop does not care where the digits come from. For a digit array stored most significant first, iterate indices from the end; for "plus one" the loop can stop as soon as the carry becomes 0, so most calls touch only the last digit. For linked lists stored least significant first, walk both lists in step and create result nodes as you go. When the lists are stored most significant first, either reverse both lists, push the digits onto two stacks, or pad the shorter list and recurse so that carries travel back up the call stack.

Complexity

Addition, subtraction and comparison are O(n + m). Schoolbook multiplication is O(n * m) time and O(n + m) space. Division by a small integer is O(n). Faster multiplication (Karatsuba, FFT-based) exists but is beyond interview scope.

Common pitfalls

• Forgetting the final carry: "999" + "1" needs a new leading digit; loop while carry is non-zero.
• Leading zeros: subtraction and multiplication can produce them; strip them but keep a single "0".
• Digit order: strings are most-significant-first while the arithmetic runs least-significant-first; reverse once, not inside the loop.
• Product length: an n-digit by m-digit product has at most n + m digits; allocate that many slots.
• Signs: handle them outside the digit routines (compare magnitudes, subtract the smaller from the larger, then fix the sign).
• Overflow of accumulated products in C++/Java when you postpone carries: res[i + j] can reach 81 * min(n, m), which fits in an int for realistic sizes, but check if n is huge.

Interview variations

• Add strings, add binary: the same loop with base 10 or 2.
• Multiply strings: position i + j accumulation.
• Plus one and add to array-form of an integer: addition where one operand is small.
• Add two numbers with digits stored in linked lists, in reverse order (direct) or in forward order (reverse the lists or use stacks).
• Huge number modulo k or check divisibility of a numeric string: keep only the running remainder.
• Factorial of a large n: repeated multiplication of a digit array by a small integer.