# LeetCode 273: Integer to English Words

## Problem Restatement

We are given a non-negative integer `num`.

Return its English words representation.

Examples:

```python
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:

```python
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:

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

## Examples

Example 1:

```python
num = 123
```

Break it into:

```python
100 + 20 + 3
```

Answer:

```python
"One Hundred Twenty Three"
```

Example 2:

```python
num = 12345
```

Break it into three-digit groups:

```python
12 | 345
```

The first group is thousands:

```python
"Twelve Thousand"
```

The second group is:

```python
"Three Hundred Forty Five"
```

Answer:

```python
"Twelve Thousand Three Hundred Forty Five"
```

Example 3:

```python
num = 1000010
```

Break it into:

```python
1 | 000 | 010
```

The middle group is zero, so we skip it.

Answer:

```python
"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:

```python
14
```

is:

```python
"Fourteen"
```

not:

```python
"One Four"
```

Also:

```python
40
```

is:

```python
"Forty"
```

not:

```python
"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:

```python
1,234,567,890
```

can be split into groups:

```python
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:

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

We can write a helper:

```python
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

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

## Walkthrough

Use:

```python
num = 1234567
```

Scales:

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

Billion chunk:

```python
1234567 // 1000000000 = 0
```

Skip.

Million chunk:

```python
1234567 // 1000000 = 1
```

Convert:

```python
1 -> "One"
```

Append scale:

```python
"One Million"
```

Remaining:

```python
1234567 % 1000000 = 234567
```

Thousand chunk:

```python
234567 // 1000 = 234
```

Convert:

```python
234 -> "Two Hundred Thirty Four"
```

Append scale:

```python
"Two Hundred Thirty Four Thousand"
```

Remaining:

```python
234567 % 1000 = 567
```

Final chunk:

```python
567 -> "Five Hundred Sixty Seven"
```

Final answer:

```python
"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:

```python
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

```python
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:

```python
if num == 0:
    return "Zero"
```

The array `below_20` handles all irregular small numbers:

```python
"Eleven", "Twelve", "Thirteen", ..., "Nineteen"
```

The array `tens` handles multiples of ten:

```python
"Twenty", "Thirty", "Forty", ..., "Ninety"
```

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

For numbers below `20`:

```python
return [below_20[n]]
```

For numbers below `100`:

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

For numbers from `100` to `999`:

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

The scale list processes the number from largest to smallest:

```python
Billion, Million, Thousand, ones
```

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

At the end:

```python
return " ".join(words)
```

creates the final string with exactly one space between words.

## Testing

```python
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 |