LeetCode 273: Integer to English Words

Problem Restatement

We are given a non-negative integer num.

Return its English words representation.

Examples:

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
0 -> "Zero"

The constraint is:

0 <= num <= 2^31 - 1

So the largest possible number is less than 2.15 billion. We only need scale words up to "Billion".

Input and Output

Item	Meaning
Input	A non-negative integer `num`
Output	English words representation
Special case	`0` becomes `"Zero"`
Largest scale needed	`"Billion"`

Example function shape:

def numberToWords(num: int) -> str:
    ...

Examples

Example 1:

num = 123

Break it into:

100 + 20 + 3

Answer:

"One Hundred Twenty Three"

Example 2:

num = 12345

Break it into three-digit groups:

12 | 345

The first group is thousands:

"Twelve Thousand"

The second group is:

"Three Hundred Forty Five"

Answer:

"Twelve Thousand Three Hundred Forty Five"

Example 3:

num = 1000010

Break it into:

1 | 000 | 010

The middle group is zero, so we skip it.

Answer:

"One Million Ten"

First Thought: Convert Digit by Digit

A tempting approach is to read every digit from left to right and attach words.

But English number names do not work one digit at a time.

For example:

is:

"Fourteen"

not:

"One Four"

Also:

is:

"Forty"

not:

"Four Ten"

So we need special handling for numbers below 20, tens, hundreds, and large scale words.

Key Insight

English number names repeat every three digits.

The number:

1,234,567,890

can be split into groups:

1 | 234 | 567 | 890

Each group is a number from 0 to 999.

Then we attach scale words:

Group	Scale
`1`	Billion
`234`	Million
`567`	Thousand
`890`	Empty

So the main problem becomes:

Convert a number from 1 to 999 into English words.

Then combine the chunks.

Converting a Number Below 1000

For any number below 1000:

Range	Rule
`1..19`	Direct word lookup
`20..99`	Tens word plus optional ones word
`100..999`	Ones word + `"Hundred"` + optional remainder

Examples:

7   -> "Seven"
18  -> "Eighteen"
42  -> "Forty Two"
305 -> "Three Hundred Five"
999 -> "Nine Hundred Ninety Nine"

We can write a helper:

helper(n)

where 0 <= n < 1000.

It returns a list of words for that chunk.

Returning a list is cleaner than returning a partially spaced string. At the end we join all words with one space.

Algorithm

If num == 0, return "Zero".
Define word arrays:
- below_20
- tens
Define scale groups:
- Billion: 1_000_000_000
- Million: 1_000_000
- Thousand: 1_000
- Empty: 1
For each scale from largest to smallest:
- Compute the current chunk:
  chunk = num // scale
- If chunk == 0, skip it.
- Convert chunk using helper.
- Append the scale word if it exists.
- Reduce:
  num %= scale
Join all words with spaces.

Walkthrough

Use:

num = 1234567

Scales:

Billion = 1_000_000_000
Million = 1_000_000
Thousand = 1_000

Billion chunk:

1234567 // 1000000000 = 0

Skip.

Million chunk:

1234567 // 1000000 = 1

Convert:

1 -> "One"

Append scale:

"One Million"

Remaining:

1234567 % 1000000 = 234567

Thousand chunk:

234567 // 1000 = 234

Convert:

234 -> "Two Hundred Thirty Four"

Append scale:

"Two Hundred Thirty Four Thousand"

Remaining:

234567 % 1000 = 567

Final chunk:

567 -> "Five Hundred Sixty Seven"

Final answer:

"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Correctness

Every integer from 1 to 2^31 - 1 can be uniquely split into three-digit chunks:

billions, millions, thousands, ones

Each nonzero chunk contributes its own English phrase, followed by the correct scale word.

The helper correctly converts every value from 1 to 999.

For values below 20, it uses the direct English word. For values below 100, it combines the tens word and the optional ones word. For values at least 100, it writes the hundreds part first, then recursively converts the remainder.

The main function processes chunks from largest scale to smallest scale, so the words appear in the correct English order.

Zero chunks are skipped, which avoids phrases such as "Zero Thousand".

Therefore the algorithm returns exactly the English words representation of num.

Complexity

Metric	Value	Why
Time	`O(1)`	The input is bounded by `2^31 - 1`, so there are at most four chunks
Space	`O(1)`	The number of produced words is bounded by a small constant

More generally, for an integer with d digits, the work is O(d).

Implementation

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0:
            return "Zero"

        below_20 = [
            "",
            "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",
        ]

        def helper(n: int) -> list[str]:
            if n == 0:
                return []

            if n < 20:
                return [below_20[n]]

            if n < 100:
                return [tens[n // 10]] + helper(n % 10)

            return [below_20[n // 100], "Hundred"] + helper(n % 100)

        scales = [
            (1_000_000_000, "Billion"),
            (1_000_000, "Million"),
            (1_000, "Thousand"),
            (1, ""),
        ]

        words = []

        for value, name in scales:
            chunk = num // value

            if chunk == 0:
                continue

            words.extend(helper(chunk))

            if name:
                words.append(name)

            num %= value

        return " ".join(words)

Code Explanation

The special case for zero is required:

if num == 0:
    return "Zero"

The array below_20 handles all irregular small numbers:

"Eleven", "Twelve", "Thirteen", ..., "Nineteen"

The array tens handles multiples of ten:

"Twenty", "Thirty", "Forty", ..., "Ninety"

The helper returns a list of words for one chunk below 1000.

For numbers below 20:

return [below_20[n]]

For numbers below 100:

return [tens[n // 10]] + helper(n % 10)

For numbers from 100 to 999:

return [below_20[n // 100], "Hundred"] + helper(n % 100)

The scale list processes the number from largest to smallest:

Billion, Million, Thousand, ones

For each nonzero chunk, we append the chunk words and then the scale word.

At the end:

return " ".join(words)

creates the final string with exactly one space between words.

Testing

def run_tests():
    s = Solution()

    assert s.numberToWords(0) == "Zero"
    assert s.numberToWords(5) == "Five"
    assert s.numberToWords(13) == "Thirteen"
    assert s.numberToWords(20) == "Twenty"
    assert s.numberToWords(42) == "Forty Two"
    assert s.numberToWords(100) == "One Hundred"
    assert s.numberToWords(305) == "Three Hundred Five"
    assert s.numberToWords(123) == "One Hundred Twenty Three"
    assert s.numberToWords(12345) == "Twelve Thousand Three Hundred Forty Five"
    assert s.numberToWords(1234567) == (
        "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
    )
    assert s.numberToWords(1000010) == "One Million Ten"
    assert s.numberToWords(2147483647) == (
        "Two Billion One Hundred Forty Seven Million "
        "Four Hundred Eighty Three Thousand Six Hundred Forty Seven"
    )

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`0`	Special case
`5`	Single digit
`13`	Teen word
`20`	Exact tens
`42`	Tens plus ones
`100`	Exact hundred
`305`	Hundred with skipped tens
`123`	Official small example
`12345`	Thousands group
`1234567`	Million and thousand groups
`1000010`	Zero chunk skipped
`2147483647`	Upper 32-bit boundary