Integer To English Words

XXX.Number to Words

String

Simulation

Problem Statement:

Convert a non-negative integer into its English words representation. For example, given 123, return "One Hundred Twenty Three". Assume the input does not exceed 2³¹ - 1.

Algorithm:

1. Handle the special case of zero by returning "Zero".
2. Break the number into groups of three digits, starting from the least significant digits (thousands, millions, etc.).
3. Use a helper function to convert each group of three digits to words:
   • Numbers less than 20 are directly mapped to their English words.
   • Numbers less than 100 are split into tens and units.
   • Numbers less than 1000 are processed by splitting into hundreds, tens, and units.
4. Combine the English words for each group with their corresponding place value (e.g., "Thousand", "Million").
5. Trim any extra spaces and return the result.

Complexity:

Time: O(n), where n is the number of digits in the number. Each digit is processed a constant number of times. | Space: O(1), as no additional data structures are used apart from a few fixed arrays.

Java Implementation:

class Solution {
    private final String[] LESS_THAN_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"; // Special case for zero

        int i = 0; // Tracks the place value (thousands, millions, etc.)
        String words = ""; // Resultant English words representation
        
        // Process each group of three digits
        while (num > 0) {
            if (num % 1000 != 0) // Only process non-zero groups
                words = helper(num % 1000) + THOUSANDS[i] + " " + words;
            num /= 1000; // Move to the next higher place value
            i++;
        }
        return words.trim(); // Remove any trailing spaces
    }
    
    private String helper(int num) {
        if (num == 0) return ""; // Base case for recursion
        
        if (num < 20) // Numbers less than 20 are directly mapped
            return LESS_THAN_20[num] + " ";
        
        if (num < 100) // Split tens and units
            return TENS[num / 10] + " " + helper(num % 10);
        
        // Split hundreds, tens, and units
        return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);
    }
}
                

Python Implementation:

class Solution:
    def __init__(self):
        self.less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
                             "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        self.tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        self.thousands = ["", "Thousand", "Million", "Billion"]

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

        i = 0
        words = ""
        while num > 0:
            if num % 1000 != 0:
                words = self.helper(num % 1000) + self.thousands[i] + " " + words
            num //= 1000
            i += 1
        return words.strip()

    def helper(self, num: int) -> str:
        if num == 0:
            return ""
        if num < 20:
            return self.less_than_20[num] + " "
        if num < 100:
            return self.tens[num // 10] + " " + self.helper(num % 10)
        return self.less_than_20[num // 100] + " Hundred " + self.helper(num % 100)
                

C++ Implementation:

class Solution {
    vector less_than_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", 
                                   "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", 
                                   "Seventeen", "Eighteen", "Nineteen"};
    vector tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    vector thousands = {"", "Thousand", "Million", "Billion"};

public:
    string numberToWords(int num) {
        if (num == 0) return "Zero";
        int i = 0;
        string words = "";
        while (num > 0) {
            if (num % 1000 != 0)
                words = helper(num % 1000) + thousands[i] + " " + words;
            num /= 1000;
            i++;
        }
        return trim(words);
    }

    string helper(int num) {
        if (num == 0) return "";
        if (num < 20) return less_than_20[num] + " ";
        if (num < 100) return tens[num / 10] + " " + helper(num % 10);
        return less_than_20[num / 100] + " Hundred " + helper(num % 100);
    }

    string trim(const string& str) {
        auto start = str.find_first_not_of(' ');
        auto end = str.find_last_not_of(' ');
        return str.substr(start, end - start + 1);
    }
};