Integer to English words, built up by range

Question: Integer to English words, built up by range

Companies: Microsoft

Difficulty: Medium

Problem statement

Write a function that spells out an integer in English words. The interviewer adds the ranges in parts, and later parts should reuse earlier ones, so design for extension from the start.

1. Digits. digit_to_words(n) for 0 <= n <= 9. Raise an error for anything else.
2. Two digits. Extend to 0 <= n <= 99. Watch the irregular words for 10-19.
3. Three digits. Extend to 0 <= n <= 999.
4. Full range. number_to_words(num) for any 32-bit signed integer, using the scale words Thousand, Million and Billion.
5. Negatives. A negative number starts with the word "Negative".

Output format

• Words are capitalized and separated by single spaces, with no leading or trailing space.
• No "and", no hyphens, and no commas ("Sixty Two", not "sixty-two").
• Zero parts are left out: 40 is "Forty", and 3,000,020 is "Three Million Twenty". Only the input 0 itself produces "Zero".

Examples

digit_to_words(6)         -> "Six"
number_to_words(17)       -> "Seventeen"
number_to_words(804)      -> "Eight Hundred Four"
number_to_words(3000020)  -> "Three Million Twenty"
number_to_words(-91512)   -> "Negative Ninety One Thousand Five Hundred Twelve"

Constraints

• -2^31 <= num <= 2^31 - 1
• Be ready to explain how you would support trillions, or a different language, with minimal changes.

Approach

The interviewer usually grows this one range at a time: digits 0–9, then 0–99, then 0–999, then everything up to about two billion, and sometimes negatives. The warm-up line "make it easy to extend" is the real test. If the 0–9 answer is a twelve-branch if chain, every later part means a rewrite. If it is a lookup table, every later part reuses it.

Part 1: 0–9. A list of ten words indexed by the digit. Reject anything out of range instead of guessing.

Part 2: 0–99. English has two irregular zones. 0–19 each have their own word ("eleven", "thirteen"), so extend the table to 20 entries. From 20 to 99 the word is a tens word plus an optional ones word: tens[n // 10] then ones[n % 10] if it is not zero. 40 is "Forty", not "Forty Zero".

Part 3: 0–999. A hundreds digit, then the 0–99 rule on the rest: ones[n // 100] + " Hundred" and, if n % 100 is not zero, the words for n % 100. This function, below_thousand, is the building block for everything after.

Part 4: full 32-bit range. Above 999, English repeats the same pattern every three digits with a scale word: "Thousand", "Million", "Billion". So split the number into groups of three digits from the right. Convert each nonzero group with below_thousand, add its scale word, and join the groups from most significant to least. A zero group is skipped completely, so 1,000,005 is "One Million Five", not "One Million Zero Thousand Five". Adding "Trillion" later is one more entry in the scale list.

Part 5: zero and negatives. Zero is the only number whose answer is the word "Zero", so handle it once at the top. Every lower layer then treats zero as "no words". For a negative number, convert the absolute value and put "Negative" in front. In Python abs is safe. In Java or C++, -2^31 overflows int, so widen to a 64-bit type first.

Invariants.

• Each helper returns a list of words, never a string with stray spaces. The caller joins once. This removes the usual bug of double or trailing spaces.
• A helper given 0 returns an empty list. Only the top-level function ever says "Zero".
• Scale i (0, 1, 2, ...) is the group n // 1000**i % 1000. The list of scale words is the single place that sets the supported range.

Code

from typing import List

ONES = [
    "Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight",
    "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen",
    "Sixteen", "Seventeen", "Eighteen", "Nineteen",
]
TENS = [
    "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy",
    "Eighty", "Ninety",
]
# One entry per group of three digits. Extend this list to extend the range.
SCALES = ["", "Thousand", "Million", "Billion"]
LIMIT = 1000 ** len(SCALES)  # first value we cannot name


def digit_to_words(n: int) -> str:
    """Part 1: 0-9."""
    if not 0 <= n <= 9:
        raise ValueError(f"expected a digit, got {n}")
    return ONES[n]


def _below_hundred(n: int) -> List[str]:
    """Words for 0 <= n < 100. Empty list for 0."""
    if n == 0:
        return []
    if n < 20:
        return [ONES[n]]
    words = [TENS[n // 10]]
    if n % 10:
        words.append(ONES[n % 10])
    return words


def _below_thousand(n: int) -> List[str]:
    """Words for 0 <= n < 1000. Empty list for 0."""
    words: List[str] = []
    if n >= 100:
        words += [ONES[n // 100], "Hundred"]
    return words + _below_hundred(n % 100)


def number_to_words(num: int) -> str:
    """Parts 2-5: any integer with abs(num) < 1000 ** len(SCALES)."""
    if num == 0:
        return "Zero"
    if abs(num) >= LIMIT:
        raise ValueError(f"{num} is out of range")

    words: List[str] = ["Negative"] if num < 0 else []
    n = abs(num)

    groups: List[List[str]] = []
    for scale in SCALES:
        chunk = n % 1000
        if chunk:
            group = _below_thousand(chunk)
            if scale:
                group.append(scale)
            groups.append(group)
        n //= 1000

    for group in reversed(groups):  # most significant group first
        words += group
    return " ".join(words)


if __name__ == "__main__":
    assert digit_to_words(0) == "Zero"
    assert digit_to_words(7) == "Seven"
    assert number_to_words(0) == "Zero"
    assert number_to_words(13) == "Thirteen"
    assert number_to_words(40) == "Forty"
    assert number_to_words(58) == "Fifty Eight"
    assert number_to_words(100) == "One Hundred"
    assert number_to_words(305) == "Three Hundred Five"
    assert number_to_words(999) == "Nine Hundred Ninety Nine"
    assert number_to_words(1000) == "One Thousand"
    assert number_to_words(1_000_005) == "One Million Five"
    assert number_to_words(20_017_300) == "Twenty Million Seventeen Thousand Three Hundred"
    assert number_to_words(2**31 - 1) == (
        "Two Billion One Hundred Forty Seven Million Four Hundred Eighty Three "
        "Thousand Six Hundred Forty Seven"
    )
    assert number_to_words(-2**31) == (
        "Negative Two Billion One Hundred Forty Seven Million Four Hundred "
        "Eighty Three Thousand Six Hundred Forty Eight"
    )
    assert number_to_words(-12) == "Negative Twelve"
    for bad in (10, -1):
        try:
            digit_to_words(bad)
            raise AssertionError("expected ValueError")
        except ValueError:
            pass
    print("ok")

Complexity

• digit_to_words: O(1) time and space.
• number_to_words: O(G) time and space, where G is the number of three-digit groups (at most len(SCALES), so 4 for 32-bit input). Each group adds at most 5 words, so the output length is bounded by a constant for a fixed range. In general it is O(log₁₀ n).
• The tables are constant-size and built once.

Test cases

• digit_to_words(0) → "Zero"; digit_to_words(9) → "Nine"; digit_to_words(10) → ValueError.
• 0 → "Zero" (the only input that produces this word).
• 7 → "Seven"; 13 → "Thirteen"; 19 → "Nineteen" (the irregular zone).
• 20 → "Twenty"; 40 → "Forty" (no trailing "Zero", and spelled without a "u").
• 58 → "Fifty Eight".
• 100 → "One Hundred"; 305 → "Three Hundred Five"; 999 → "Nine Hundred Ninety Nine".
• 1000 → "One Thousand"; 1010 → "One Thousand Ten".
• 1000005 → "One Million Five" (zero middle group skipped).
• 20017300 → "Twenty Million Seventeen Thousand Three Hundred".
• 2147483647 → "Two Billion One Hundred Forty Seven Million Four Hundred Eighty Three Thousand Six Hundred Forty Seven".
• -12 → "Negative Twelve"; -2147483648 → ends in "... Six Hundred Forty Eight" (no overflow).
• 10**12 → ValueError until "Trillion" is added to SCALES.

Follow-ups

• Larger numbers (trillions and beyond). Append to SCALES. No logic changes. This is the payoff of the table-driven design, and a good place to say so.
• British style with "and". "One Hundred and Five", "One Thousand and Five". Insert "and" before the final _below_hundred part when something comes before it, either a hundreds digit in the same group or a higher group. Keep it behind a style flag so both outputs share one core.
• Ordinals ("Twenty First", "One Hundredth"). Convert the cardinal, then rewrite only the last word with an ordinal table (One → First, Two → Second, Twelve → Twelfth, Twenty → Twentieth, Hundred → Hundredth, and so on). Everything earlier stays the same.
• Decimals or currency. "Twelve Dollars and Five Cents" or "Three Point One Four". Split on the decimal point. Convert the integer part as before, then either read the fraction digit by digit (reusing digit_to_words) or as a whole number of cents.
• Other languages or the reverse direction. Move the tables into a per-locale config. Note that some languages break the three-digit rule (Indian English uses lakh and crore after the first thousand, so groups become 3, then 2, 2, ...). Make the grouping widths part of the locale. For words → number, tokenize and keep a running total: add small values, multiply by "Hundred", and for a scale word add current * scale to the total and reset current.

Interviewer expectations

Mid-level (L4)

• Gets 0–9 and 0–99 right, including 11–19 and "Forty" with no "Zero" tail.
• Reaches the three-digit group idea for the full range, perhaps with a hint.
• Handles 0 and output spacing correctly, and tests with a few round numbers.

Senior (L5)

• Starts table-driven from Part 1 and explains why: each later part reuses the earlier ones.
• Writes one below_thousand helper and reuses it for every group. Skips zero groups without being told.
• Names the edge cases unprompted: 0, 10/1000 boundaries, 1,000,005, INT_MIN overflow in fixed-width languages. Rejects out-of-range input explicitly.

Staff (L6+)

• Treats the supported range as data (the scale list), so extending it is a config change, and separates number logic from language tables.
• Discusses localization honestly: "and" rules, ordinals, non-thousand grouping such as lakh/crore, and that a real product would use a library such as ICU's RuleBasedNumberFormat.
• Shows the test plan as a table of boundary values and proposes a round-trip check (words → number → words) as a property test.