Problem Description

Given a non-negative integer num, convert it to its English words representation.

• The input num is guaranteed to be less than 231 (i.e., it fits in a 32-bit signed integer).
• The output should be a string containing the English words for the number, separated by single spaces, and without leading or trailing spaces.
• The function should handle zero, all numbers up to billions, and should not use "and" (e.g., "One Hundred Twenty Three" not "One Hundred and Twenty Three").
• There is only one valid way to express each number in words.

Thought Process

Converting an integer to English words is a problem that requires breaking the number into manageable chunks and mapping those to their word equivalents. At first, one might consider handling each digit individually, but this quickly becomes unwieldy due to the irregularities in English (like "Eleven", "Twenty", "Hundred", "Thousand", etc.).

A more systematic approach is to process the number in groups of three digits (hundreds), since English words for numbers are naturally grouped this way (e.g., "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven").

We also need to handle special cases for numbers less than 20, as these have unique names (e.g., "Thirteen" instead of "Ten Three"). By mapping these cases and building up the number recursively or iteratively, we can construct the English phrase step by step.

Solution Approach

• Step 1: Define Mappings
  • Create arrays or lists to map numbers less than 20, the tens (20, 30, ..., 90), and the thousands units ("Thousand", "Million", "Billion").
• Step 2: Handle Zero
  • If num is zero, immediately return "Zero".
• Step 3: Process in Chunks of Three Digits
  • Repeatedly extract the last three digits from num (using modulo and integer division).
  • For each chunk, if it's not zero, convert it to words and append the appropriate thousands unit (e.g., "Thousand", "Million", etc.).
• Step 4: Convert Three-Digit Chunks
  • For numbers less than 20, return the mapped word.
  • For numbers less than 100, recursively process the tens and units.
  • For numbers 100 or greater, process the hundreds digit, then recursively process the remainder.
• Step 5: Assemble the Final Result
  • Combine the processed chunks in the correct order, trimming extra spaces.

This approach ensures that each part of the number is handled according to English language rules, and that the solution is both efficient and readable.

Example Walkthrough

Let's walk through the conversion of num = 1234567:

1. Break into chunks of three digits from right: 1,234,567 → [1], [234], [567]
2. Chunk 1: 567
   • 567 = 5 * 100 + 67
   • Process "Five Hundred"
   • Process 67: "Sixty Seven"
   • Result: "Five Hundred Sixty Seven"
3. Chunk 2: 234
   • 234 = 2 * 100 + 34
   • Process "Two Hundred"
   • Process 34: "Thirty Four"
   • Result: "Two Hundred Thirty Four"
   • Add "Thousand": "Two Hundred Thirty Four Thousand"
4. Chunk 3: 1
   • Process "One"
   • Add "Million": "One Million"
5. Combine in order: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Code 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 = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        thousands = ["", "Thousand", "Million", "Billion"]

        def helper(n):
            if n == 0:
                return ""
            elif n < 20:
                return below_20[n] + " "
            elif n < 100:
                return tens[n // 10] + " " + helper(n % 10)
            else:
                return below_20[n // 100] + " Hundred " + helper(n % 100)

        res = ""
        for i, unit in enumerate(thousands):
            if num % 1000 != 0:
                res = helper(num % 1000) + unit + " " + res
            num //= 1000
        return res.strip()
      

class Solution {
public:
    string numberToWords(int num) {
        if (num == 0) return "Zero";
        vector<string> below_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
                                  "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        vector<string> tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        vector<string> thousands = {"", "Thousand", "Million", "Billion"};
        string res;
        int i = 0;
        while (num > 0) {
            if (num % 1000 != 0) {
                res = helper(num % 1000, below_20, tens) + thousands[i] + (res.empty() ? "" : " ") + res;
            }
            num /= 1000;
            i++;
        }
        // Remove leading/trailing spaces
        while (!res.empty() && res.back() == ' ') res.pop_back();
        return res;
    }
private:
    string helper(int n, vector<string>& below_20, vector<string>& tens) {
        if (n == 0) return "";
        else if (n < 20) return below_20[n] + " ";
        else if (n < 100) return tens[n / 10] + " " + helper(n % 10, below_20, tens);
        else return below_20[n / 100] + " Hundred " + helper(n % 100, below_20, tens);
    }
};
      

class Solution {
    private final String[] below_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
        "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private final String[] thousands = {"", "Thousand", "Million", "Billion"};
    
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        String res = "";
        int i = 0;
        while (num > 0) {
            if (num % 1000 != 0) {
                res = helper(num % 1000) + thousands[i] + " " + res;
            }
            num /= 1000;
            i++;
        }
        return res.trim();
    }
    
    private String helper(int n) {
        if (n == 0) return "";
        else if (n < 20) return below_20[n] + " ";
        else if (n < 100) return tens[n / 10] + " " + helper(n % 10);
        else return below_20[n / 100] + " Hundred " + helper(n % 100);
    }
}
      

var numberToWords = function(num) {
    if (num === 0) return "Zero";
    const below_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
        "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"];
    const tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"];
    const thousands = ["", "Thousand", "Million", "Billion"];
    
    function helper(n) {
        if (n === 0) return "";
        else if (n < 20) return below_20[n] + " ";
        else if (n < 100) return tens[Math.floor(n / 10)] + " " + helper(n % 10);
        else return below_20[Math.floor(n / 100)] + " Hundred " + helper(n % 100);
    }
    
    let res = "";
    let i = 0;
    while (num > 0) {
        if (num % 1000 !== 0) {
            res = helper(num % 1000) + thousands[i] + " " + res;
        }
        num = Math.floor(num / 1000);
        i++;
    }
    return res.trim();
};
      

Time and Space Complexity

• Brute-force Approach:
  • If you tried to build the string digit by digit, the complexity would be unnecessarily high due to repeated string manipulation and handling of English irregularities.
• Optimized Approach:
  • Time Complexity: O(1) — The number of operations is bounded because the number of digits in a 32-bit integer is limited (maximum 10 digits). Each digit or group is processed a constant number of times.
  • Space Complexity: O(1) — The extra space used for mappings and the result string does not scale with input size.

Summary

The solution to the integer-to-English-words problem involves breaking the number into three-digit chunks, mapping those to English words using pre-defined arrays, and assembling the final string with the appropriate "Thousand", "Million", and "Billion" suffixes. By handling the special cases (numbers below 20) and using recursion or iteration, we achieve a clean and efficient solution that mirrors how numbers are spoken in English. The approach is elegant because it leverages the natural structure of the language and avoids unnecessary complexity.