Integer to English Words

Convert a non-negative integer num to its English words representation.

Example 1:

Input: num = 123 Output: “One Hundred Twenty Three”

Example 2:

Input: num = 12345 Output: “Twelve Thousand Three Hundred Forty Five”

Example 3:

Input: num = 1234567 Output: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

Constraints:

• 0 <= num <= 231 - 1

Approach: Recursive Grouping by Thousands

Algorithm

1. Handle the special case num == 0 returning "Zero"
2. Split the number into groups of three digits (units, thousands, millions, billions)
3. For each group, convert the three-digit number to words and append the group’s scale word
4. Convert a three-digit number: handle hundreds, then tens and units with the special teens words
5. Join the parts with spaces

Time & Space Complexity

• Time Complexity: O(1) - at most four groups (billions) are processed
• Space Complexity: O(1) - constant-length lookup arrays and small output

Java Implementation

public class IntegerToEnglishWords {

    private static final String[] ONES = {
        "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine",
        "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
        "Seventeen", "Eighteen", "Nineteen"
    };

    private static final String[] TENS = {
        "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
    };

    private static final String[] SCALES = {"", "Thousand", "Million", "Billion"};

    /**
     * Convert a non-negative integer to its English words representation.
     * @param num Input integer
     * @return English words
     */
    public static String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }

        StringBuilder result = new StringBuilder();
        int group = 0;

        while (num > 0) {
            int threeDigits = num % 1000;
            if (threeDigits != 0) {
                String words = convertThree(threeDigits);
                result.insert(0, words + (SCALES[group].isEmpty() ? "" : " " + SCALES[group]) + " ");
            }
            num /= 1000;
            group++;
        }

        return result.toString().trim();
    }

    private static String convertThree(int n) {
        StringBuilder sb = new StringBuilder();

        int hundred = n / 100;
        if (hundred > 0) {
            sb.append(ONES[hundred]).append(" Hundred ");
        }

        int rest = n % 100;
        if (rest >= 20) {
            sb.append(TENS[rest / 10]);
            if (rest % 10 > 0) {
                sb.append(" ").append(ONES[rest % 10]);
            }
        } else if (rest > 0) {
            sb.append(ONES[rest]);
        }

        return sb.toString().trim();
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: num = 123");
        System.out.println("Output: \"" + numberToWords(123) + "\"");
        // Expected: "One Hundred Twenty Three"

        System.out.println("Input: num = 12345");
        System.out.println("Output: \"" + numberToWords(12345) + "\"");
        // Expected: "Twelve Thousand Three Hundred Forty Five"

        System.out.println("Input: num = 1234567");
        System.out.println("Output: \"" + numberToWords(1234567) + "\"");
        // Expected: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
    }
}

Example Walkthrough

For num = 1234567:

1. Group 0: 567 -> “Five Hundred Sixty Seven”
2. Group 1: 234 -> “Two Hundred Thirty Four Thousand”
3. Group 2: 1 -> “One Million”
4. Combine: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

Key Points

1. Grouping by Thousands: Every three digits get a scale word (Thousand, Million, Billion)
2. Teens Table: Numbers 0-19 need dedicated words (eleven, twelve, …)
3. Recursion or Iteration: Grouping can be handled recursively or with a loop
4. Skip Zero Groups: Groups equal to zero contribute no words
5. Max Value: 231 - 1 = 2,147,483,647, so Billions is the largest scale needed