LeetCode Solutions Blog

Integer to English Words

Number: 273

Difficulty: Hard

Paid? No

Problem Description

Given a non-negative integer, convert it to its English words representation. For example, 123 should be converted to "One Hundred Twenty Three", and 1234567 should be converted to "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven". The integer range is 0 to 2^31 - 1.

Key Insights

The number is processed in groups of three digits (hundreds, tens, and ones), mapping these groups to their word equivalents.
Special handling is required for numbers between 10 and 19 (teens) because they have unique names.
Larger groups beyond the basic hundred (thousand, million, billion) need to be appended with the appropriate scale.
The solution is recursive or iterative in nature, processing each three-digit block separately and then combining them.
Edge case: when the number is 0, the output should simply be "Zero".

Space and Time Complexity

Time Complexity: O(1) — Although it appears to depend on the number of digits, the maximum input size is fixed (at most 10 digits for 2^31 - 1). Space Complexity: O(1) — Only a constant amount of extra space is used.

Solution

The solution involves breaking the integer into segments of three digits starting from the least significant digits. For each segment:

Convert the hundreds, tens, and ones place into words.
Handle the special case for numbers between 10 and 19.
Append the appropriate scale (thousand, million, billion) based on the segment’s position. The final result is constructed by concatenating the word representations of these segments (ignoring empty segments) in reverse order (most significant segment first).

Data Structures used:

Arrays or lists for mapping digits, teens, tens and scales.

Algorithmic Approach:

Define helper functions that convert a three-digit number into words.
Loop through each segment (every three digits) and convert if non-zero.
Concatenate segments with proper scale values.
Trim any extra spaces from the final output.

Code Solutions

# Define mappings for number words
ones = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
teens = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
tens = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
scales = ["", "Thousand", "Million", "Billion"]

def three_digit_to_words(num):
    # Convert a number less than 1000 to words
    if num == 0:
        return ""
    result = ""
    # Handle hundreds place
    if num >= 100:
        result += ones[num // 100] + " Hundred "
        num %= 100
    # Handle tens and ones
    if num >= 20:
        result += tens[num // 10] + " "
        num %= 10
    elif num >= 10:  # Handle teen numbers specifically
        result += teens[num - 10] + " "
        num = 0
    # Handle remaining ones (if any)
    if num > 0:
        result += ones[num] + " "
    return result

def number_to_words(num):
    # Special case: if number is 0, return "Zero"
    if num == 0:
        return "Zero"
    
    words = ""
    scale_index = 0
    # Process each group of 3 digits
    while num > 0:
        current_chunk = num % 1000  # take last three digits
        if current_chunk != 0:
            # Convert the current chunk and add the corresponding scale
            words = three_digit_to_words(current_chunk) + scales[scale_index] + " " + words
        num //= 1000
        scale_index += 1
        
    # Return the cleaned up result
    return words.strip()

# Example Usage:
print(number_to_words(123))       # Output: "One Hundred Twenty Three"
print(number_to_words(12345))     # Output: "Twelve Thousand Three Hundred Forty Five"
print(number_to_words(1234567))   # Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"