Digits, bases and numbers as strings

Many coding-round problems treat a number as a row of digits: reverse an integer, name a spreadsheet column, or multiply values too long for any built-in type. Digits come off the right end with % 10 and integer division, and an overflow can be caught before the multiplication by 10 that causes it. Spreadsheet column titles, as in the Excel sheet column title problem, are numerals with digits from 1 to 26, called bijective base 26, so converting between bases needs one change. Long numbers stay strings of digits, carried by hand as on paper.

Three problems about digits

Problem A: reverse the digits of a 32-bit integer. Given x with −2³¹ ≤ x ≤ 2³¹ − 1, return its digits reversed, with its sign, or 0 if that does not fit in 32 bits, using no 64-bit type.

• 1,463,847,412 gives 2,147,483,641, just inside the limit, and −120 gives −21.
• 1,563,847,412 gives 0, because 2,147,483,651 is too large.

Problem B: spreadsheet column titles, both ways. Columns are named A to Z, then AA to AZ, BA and on to ZZ, then AAA. Write column_title(n) for 1 ≤ n ≤ 2³¹ − 1 and column_number(title) for the way back.

• 1 is A, 26 is Z, 27 is AA, 702 is ZZ and 703 is AAA.
• 16,384, the number of columns of an Excel worksheet, is XFD.

Problem C: multiply two numbers as strings. Given two non-negative integers as decimal strings of up to 5,000 digits, return their product as a string without leading zeros, converting neither to a big integer.

• "128" × "64" is "8192", "0" × "98765" is "0", and "99" × "99" is "9801".

The brute force, and where it breaks

Problem B can count: start at A and add one, like an odometer, n − 1 times. That takes 17,037 letter changes for 16,384 and over 2.2 billion for 2³¹ − 1. Problem C can add the first number to itself as often as the second says: 64 additions for "128" × "64", but around 10⁵⁰⁰⁰ for 5,000 digits. Problem A has no slow version, only a wrong one: digits reversed inside a 32-bit int wrap around silently in Java, C++ and Go.

# The obvious approach to each of the three problems, with the work it does counted.

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


def as_int32(v):
    """What a 32-bit signed int holds after v: Java and Go keep the low 32 bits of a result that overflows."""
    return (v - INT_MIN) % 2**32 + INT_MIN


def reverse_in_int32(x):
    """Problem A, naively: reverse the digits inside a 32-bit int, as Java would, with no overflow check."""
    r = 0
    while x != 0:
        d = abs(x) % 10 if x > 0 else -(abs(x) % 10)  # Java's % keeps the sign of x
        x = abs(x) // 10 if x > 0 else -(abs(x) // 10)  # and its / rounds towards zero
        r = as_int32(r * 10 + d)  # this multiplication is where it can overflow
    return r


def title_by_counting(n):
    """Problem B, slowly: start at A and add one, like an odometer, n - 1 times. Returns the title and the letters changed."""
    letters = ["A"]
    changed = 0
    for _ in range(n - 1):
        i = len(letters) - 1
        while i >= 0 and letters[i] == "Z":  # a Z rolls over to A and carries one to the left
            letters[i] = "A"
            changed += 1
            i -= 1
        if i < 0:
            letters.insert(0, "A")  # ZZ + 1 is AAA: the title grows by a letter
        else:
            letters[i] = chr(ord(letters[i]) + 1)
        changed += 1
    return "".join(letters), changed


def multiply_by_adding(a, b):
    """Problem C, slowly: add a to itself int(b) times. Returns the product and the number of additions."""
    total = 0
    additions = 0
    for _ in range(int(b)):
        total += int(a)
        additions += 1
    return str(total), additions


print("Problem A: reversed inside a 32-bit int, with no check")
for x in (1463847412, -120, 1563847412, 1000000003):
    print(f"  {x:>14,} -> {reverse_in_int32(x):>14,}")

print("Problem B: counting up from A")
for n in (28, 703, 16384):
    title, changed = title_by_counting(n)
    print(f"  {n:>6,} -> {title:<4} after {changed:,} letter changes")

print("Problem C: repeated addition")
for a, b in (("128", "64"), ("99", "99")):
    product, additions = multiply_by_adding(a, b)
    print(f"  {a} x {b} = {product} after {additions} additions")

try:
    int("9" * 5000)
except ValueError as e:
    print("int() of a 5,000-digit string:", str(e).split(":")[0])

Problem A: reversed inside a 32-bit int, with no check
   1,463,847,412 ->  2,147,483,641
            -120 ->            -21
   1,563,847,412 -> -2,147,483,645
   1,000,000,003 -> -1,294,967,295
Problem B: counting up from A
      28 -> AB   after 28 letter changes
     703 -> AAA  after 730 letter changes
  16,384 -> XFD  after 17,037 letter changes
Problem C: repeated addition
  128 x 64 = 8192 after 64 additions
  99 x 99 = 9801 after 99 additions
int() of a 5,000-digit string: Exceeds the limit (4300 digits) for integer string conversion

The run shows the wrap-around, −2,147,483,645 instead of 0, and why Python’s shortcut is closed: since version 3.11, int() refuses decimal strings of over 4,300 digits by default.

What to notice

• Digits leave from the right. Compare the running result with a tenth of the limit before multiplying by 10, and no overflow can happen.
• A column title has digits 1 to 26. Z is a digit worth 26 and no title contains a zero, so ZZ plus one is AAA, where decimal 99 plus one is 100. Other bases use remainders from 0 up.
• A product of m and n digits has at most m + n digits, so multiplying numbers as strings, digit by digit, needs only m × n digit products and one pass of carries.

Reversing digits with the check before the multiplication Pro: opens with a Pro, Premium or Ultimate pass