LeetCode 273 - Integer to English Words

The problem asks us to convert a non-negative integer into its English words representation. Instead of returning digits such as 12345, we must produce a properly formatted English phrase such as "Twelve Thousand Three Hundred Forty Five".

leetcodehardmathstringrecursion

LeetCode Problem 273

Difficulty: 🔴 Hard
Topics: Math, String, Recursion

Solution

Problem Understanding

The problem asks us to convert a non-negative integer into its English words representation. Instead of returning digits such as 12345, we must produce a properly formatted English phrase such as "Twelve Thousand Three Hundred Forty Five".

The input is a single integer num where:

  • 0 <= num <= 2^31 - 1
  • The maximum possible value is 2147483647

The output must follow standard English naming conventions for numbers. This includes handling:

  • Units such as One, Two, Three
  • Tens such as Twenty, Thirty, Forty
  • Special numbers from 10 to 19
  • Scale words such as Thousand, Million, and Billion

The most important observation is that English numbers are naturally grouped into chunks of three digits. For example:

  • 1,234,567
  • 1 million
  • 234 thousand
  • 567

Each three-digit group can be translated independently and then combined with the correct scale word.

The constraints are small from a computational perspective because even the largest possible integer contains at most ten digits. This means performance is not about handling massive input sizes, but rather about implementing the conversion logic correctly and cleanly.

Several edge cases can easily cause bugs in naive implementations:

  • 0 must return "Zero" directly
  • Numbers between 10 and 19 use unique English words
  • Tens like 20, 30, 40 must not include trailing unit words
  • Exact hundreds such as 100 should not produce extra spaces
  • Groups containing zeros, such as 1000010, should skip empty sections cleanly
  • The largest possible value must still be formatted correctly

A correct solution must carefully handle spacing, scale words, and special naming rules.

Approaches

Brute Force Approach

A brute-force approach would attempt to hardcode or directly simulate every possible number pattern using many conditional branches. For example, we could separately handle:

  • One-digit numbers
  • Two-digit numbers
  • Three-digit numbers
  • Thousands
  • Millions
  • Billions

This approach would repeatedly decompose the number and manually concatenate words for each special case.

While this method can eventually produce the correct answer, it quickly becomes difficult to maintain and error-prone. English number formatting contains many exceptions, especially for numbers between 10 and 19, and handling all combinations manually leads to deeply nested conditionals.

The brute-force method also duplicates logic because the same conversion rules apply repeatedly to every three-digit block.

Key Insight for the Optimal Solution

The key observation is that English numbers follow a recursive structure based on groups of three digits.

Every number can be decomposed into chunks such as:

  • Billions
  • Millions
  • Thousands
  • Hundreds

Each chunk contains at most three digits, and every three-digit number follows the exact same conversion rules.

For example:

  • 1234567
  • 1 million
  • 234 thousand
  • 567

If we create a helper function that converts any number from 1 to 999 into English words, we can repeatedly apply it to each chunk and append the appropriate scale word.

This dramatically simplifies the implementation because:

  • We solve one small subproblem cleanly
  • We reuse the same logic for every chunk
  • The recursion naturally mirrors English number structure

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(d) O(d) Large amount of repetitive conditional logic
Optimal O(d) O(d) Processes three-digit groups recursively and cleanly

Here, d represents the number of digits in the number. Since the input size is bounded by a 32-bit integer, d is at most 10.

Algorithm Walkthrough

  1. First, handle the special case where num == 0. English representation for zero is unique and does not follow the normal grouping rules, so we immediately return "Zero".
  2. Create lookup arrays for:
  • Numbers from 1 to 19
  • Multiples of ten from 20 to 90
  • Scale words such as Thousand, Million, and Billion

These arrays allow constant-time lookup of English words. 3. Define a helper function that converts numbers from 1 to 999. 4. Inside the helper:

  • If the number is less than 20, directly return the corresponding word because these values have unique names.

  • If the number is less than 100, compute:

  • Tens digit

  • Remaining unit digit

Then combine the tens word with the recursive result of the remainder.

  • Otherwise:

  • Extract the hundreds digit

  • Append "Hundred"

  • Recursively process the remaining two digits

  1. Process the original number in chunks of three digits using repeated division and modulo operations:
  • num % 1000 extracts the current chunk
  • num //= 1000 moves to the next chunk
  1. For every non-zero chunk:
  • Convert it using the helper function
  • Append the correct scale word such as "Thousand" or "Million"
  1. Build the final result from left to right by prepending newly processed chunks.
  2. Trim extra whitespace and return the final string.

Why it works

English number naming is hierarchical and based on groups of three digits. Every chunk between 0 and 999 can be translated independently using the same rules. By correctly converting each chunk and attaching the appropriate scale word, the algorithm reconstructs the full English representation exactly as standard English grammar defines it.

Python Solution

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

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

        thousands = ["", "Thousand", "Million", "Billion"]

        def helper(n: int) -> str:
            if n == 0:
                return ""

            if n < 20:
                return below_twenty[n]

            if n < 100:
                return (
                    tens[n // 10] +
                    (" " + helper(n % 10) if n % 10 != 0 else "")
                )

            return (
                below_twenty[n // 100] +
                " Hundred" +
                (" " + helper(n % 100) if n % 100 != 0 else "")
            )

        result = []
        index = 0

        while num > 0:
            current_chunk = num % 1000

            if current_chunk != 0:
                chunk_words = helper(current_chunk)

                if thousands[index]:
                    chunk_words += " " + thousands[index]

                result.append(chunk_words)

            num //= 1000
            index += 1

        return " ".join(reversed(result))

The implementation begins with a direct check for zero because "Zero" is a special standalone case.

The arrays below_twenty, tens, and thousands serve as lookup tables for the English words. This avoids repeated conditionals and keeps the code clean.

The helper function is responsible for converting numbers from 1 to 999.

For numbers below 20, the function directly returns the corresponding word because these values have irregular English names.

For numbers below 100, the function:

  • Finds the tens digit
  • Converts the remaining unit digit recursively

For numbers greater than or equal to 100, the function:

  • Extracts the hundreds digit
  • Appends "Hundred"
  • Recursively converts the remaining portion

The main loop repeatedly extracts three-digit chunks using % 1000. Each chunk is translated independently and paired with the correct scale word from the thousands array.

Finally, the chunks are reversed because processing starts from the least significant digits.

Go Solution

package main

import "strings"

func numberToWords(num int) string {
	if num == 0 {
		return "Zero"
	}

	belowTwenty := []string{
		"", "One", "Two", "Three", "Four", "Five",
		"Six", "Seven", "Eight", "Nine", "Ten",
		"Eleven", "Twelve", "Thirteen", "Fourteen",
		"Fifteen", "Sixteen", "Seventeen", "Eighteen",
		"Nineteen",
	}

	tens := []string{
		"", "", "Twenty", "Thirty", "Forty",
		"Fifty", "Sixty", "Seventy", "Eighty", "Ninety",
	}

	thousands := []string{
		"", "Thousand", "Million", "Billion",
	}

	var helper func(int) string

	helper = func(n int) string {
		if n == 0 {
			return ""
		}

		if n < 20 {
			return belowTwenty[n]
		}

		if n < 100 {
			if n%10 == 0 {
				return tens[n/10]
			}

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

		if n%100 == 0 {
			return belowTwenty[n/100] + " Hundred"
		}

		return belowTwenty[n/100] + " Hundred " + helper(n%100)
	}

	result := []string{}
	index := 0

	for num > 0 {
		currentChunk := num % 1000

		if currentChunk != 0 {
			chunkWords := helper(currentChunk)

			if thousands[index] != "" {
				chunkWords += " " + thousands[index]
			}

			result = append([]string{chunkWords}, result...)
		}

		num /= 1000
		index++
	}

	return strings.Join(result, " ")
}

The Go implementation follows the same algorithmic structure as the Python version. The primary difference is that Go requires explicit slice handling and string concatenation.

Go does not support nested named functions as naturally as Python, so the helper function is declared using a function variable.

Another notable difference is how the result is constructed. Since Go slices do not provide a convenient reverse iterator, chunks are prepended directly into the result slice.

Worked Examples

Example 1

Input:

123

Processing steps:

Step Value Action
1 123 % 1000 = 123 Extract chunk
2 helper(123) Convert chunk
3 123 // 100 = 1 "One Hundred"
4 Remaining = 23 Convert recursively
5 23 // 10 = 2 "Twenty"
6 Remaining = 3 "Three"
7 Combine "One Hundred Twenty Three"

Final output:

One Hundred Twenty Three

Example 2

Input:

12345

Chunk decomposition:

Chunk Scale
345 ""
12 Thousand

Processing:

Step Chunk Result
1 345 "Three Hundred Forty Five"
2 12 "Twelve Thousand"
3 Combine "Twelve Thousand Three Hundred Forty Five"

Final output:

Twelve Thousand Three Hundred Forty Five

Example 3

Input:

1234567

Chunk decomposition:

Chunk Scale
567 ""
234 Thousand
1 Million

Processing:

Step Chunk Words
1 567 "Five Hundred Sixty Seven"
2 234 "Two Hundred Thirty Four Thousand"
3 1 "One Million"
4 Combine "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Final output:

One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven

Complexity Analysis

Measure Complexity Explanation
Time O(d) Each digit is processed a constant number of times
Space O(d) Recursive calls and result storage scale with digit count

The number is processed in groups of three digits, and each group requires constant work. Since a 32-bit integer contains at most 10 digits, the runtime is effectively constant in practice. The recursion depth is also bounded because the helper only processes numbers up to 999.

Test Cases

solution = Solution()

assert solution.numberToWords(0) == "Zero"  # special zero case

assert solution.numberToWords(5) == "Five"  # single digit

assert solution.numberToWords(13) == "Thirteen"  # teen number

assert solution.numberToWords(20) == "Twenty"  # exact multiple of ten

assert solution.numberToWords(45) == "Forty Five"  # tens + units

assert solution.numberToWords(100) == "One Hundred"  # exact hundred

assert solution.numberToWords(123) == "One Hundred Twenty Three"  # standard three digits

assert solution.numberToWords(1000) == "One Thousand"  # exact thousand

assert solution.numberToWords(1001) == "One Thousand One"  # zero in middle

assert solution.numberToWords(1010) == "One Thousand Ten"  # skip empty hundreds

assert solution.numberToWords(12345) == (
    "Twelve Thousand Three Hundred Forty Five"
)  # multiple chunks

assert solution.numberToWords(1000000) == (
    "One Million"
)  # exact million

assert solution.numberToWords(1000010) == (
    "One Million Ten"
)  # internal zero chunks

assert solution.numberToWords(1234567) == (
    "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
)  # large mixed number

assert solution.numberToWords(2147483647) == (
    "Two Billion One Hundred Forty Seven Million "
    "Four Hundred Eighty Three Thousand "
    "Six Hundred Forty Seven"
)  # maximum 32-bit integer
Test Why
0 Validates special handling for zero
5 Tests simple single-digit conversion
13 Verifies teen word lookup
20 Tests exact tens formatting
45 Ensures proper tens and units combination
100 Verifies exact hundred formatting
123 Standard three-digit case
1000 Exact thousand handling
1001 Ensures zeros between chunks are skipped
1010 Verifies partial chunk handling
12345 Multi-chunk conversion
1000000 Exact million handling
1000010 Internal empty chunk skipping
1234567 Complex multi-scale formatting
2147483647 Maximum valid input

Edge Cases

Input Equal to Zero

Zero is the only number that does not naturally fit into the chunk-based decomposition approach. If we attempted normal processing, no chunks would be added to the result, producing an empty string instead of "Zero".

The implementation handles this immediately at the beginning by returning "Zero" before any further logic executes.

Numbers Between 10 and 19

English names for numbers between 10 and 19 are irregular. For example:

  • 11 is "Eleven"
  • 13 is "Thirteen"

These cannot be constructed from generic tens and unit rules.

The implementation avoids errors by storing all values from 0 to 19 in a lookup table and returning them directly.

Chunks Containing Zeros

Numbers such as:

1000010

contain empty chunks in the middle. A naive implementation might accidentally generate:

One Million Thousand Ten

which is incorrect.

The algorithm solves this by skipping any chunk whose value is 0. Only non-zero chunks are converted and appended to the final result.

Exact Multiples of Hundred or Thousand

Numbers like:

  • 100
  • 1000
  • 1000000

can accidentally produce trailing spaces or unnecessary words.

The helper function carefully checks whether the remainder is zero before recursively appending additional words. This guarantees clean formatting without extra whitespace or invalid phrases.