Integer to English Words

Hard Arrays & Hashing Simulation Original on LeetCode

Integer to English Words is a hard arrays & hashing problem solved with the simulation pattern. The best approach, optimal (iterative groups of three), runs in O(1) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from recursive descent by magnitude up.

Problem

Convert a non-negative integer num into its English words, with each word capitalised and words separated by single spaces.

Use the short-scale names Thousand, Million and Billion, the word Hundred inside each three-digit group, and no “and” or hyphens (for example Forty Two, not forty-two). Groups that are entirely zero are not spoken.

Examples

Example 1

Input
num = 507
Output
"Five Hundred Seven"
Why
The zero tens digit is simply not spoken.

Example 2

Input
num = 1000010
Output
"One Million Ten"
Why
The thousands group is 000, so the word "Thousand" is skipped entirely.

Example 3

Input
num = 0
Output
"Zero"
Why
Zero is the only number that is spelled with the word "Zero".

Constraints

  • 0 <= num <= 2^31 - 1

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Recursive descent by magnitudeO(1)O(1)
Optimal (iterative groups of three)O(1)O(1)

1Recursive descent by magnitude

TimeO(1)The input has at most 10 digits, so there are a bounded number of recursive calls.
SpaceO(1)Recursion depth and output length are bounded by constants.

Write a function words(n) that peels off the largest unit it can: billions, millions, thousands, hundreds, tens, and finally the words below 20. Each case recurses on the quotient and the remainder and joins the non-empty parts with single spaces.

  1. If num == 0 return "Zero".
  2. words(n): n == 0 → ""; n < 20 → BELOW_20[n]; n < 100 → TENS[n / 10] + words(n % 10).
  3. n < 1000 → words(n / 100) + "Hundred" + words(n % 100); then the same for 10^6 (Thousand), 10^9 (Million) and the rest (Billion).
  4. Join with a helper that adds a space only between two non-empty parts.
class Solution {
    private static final String[] BELOW_20 = { "", "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" };

    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        return words(num);
    }

    private String words(int n) {
        if (n == 0) return "";
        if (n < 20) return BELOW_20[n];
        if (n < 100) return join(TENS[n / 10], words(n % 10));
        if (n < 1000) return join(words(n / 100) + " Hundred", words(n % 100));
        if (n < 1_000_000) return join(words(n / 1000) + " Thousand", words(n % 1000));
        if (n < 1_000_000_000) return join(words(n / 1_000_000) + " Million", words(n % 1_000_000));
        return join(words(n / 1_000_000_000) + " Billion", words(n % 1_000_000_000));
    }

    private String join(String a, String b) {
        if (b.isEmpty()) return a;
        return a + " " + b;
    }
}

2Optimal (iterative groups of three)

TimeO(1)At most four groups, each spelled in constant time.
SpaceO(1)A bounded number of words is stored.

Split the number into 3-digit groups from the right. Spell each non-zero group with one small helper (hundreds, then below-20 or tens + ones), append the scale word for its position ("", Thousand, Million, Billion), and put it in front of what has been built so far. Words are collected in a list and joined once, so spacing is always clean.

  1. If num == 0 return "Zero".
  2. scale = 0; while num > 0: group = num % 1000. If group > 0, build its words, add SCALES[scale] if non-empty, and prepend them to the result.
  3. num /= 1000, scale++.
  4. Join all words with single spaces.
class Solution {
    private static final String[] BELOW_20 = { "", "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" };

    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        List<String> result = new ArrayList<>();
        int scale = 0;
        while (num > 0) {
            int group = num % 1000;
            if (group > 0) {
                List<String> part = new ArrayList<>();
                if (group >= 100) {
                    part.add(BELOW_20[group / 100]);
                    part.add("Hundred");
                }
                int rest = group % 100;
                if (rest >= 20) {
                    part.add(TENS[rest / 10]);
                    if (rest % 10 > 0) part.add(BELOW_20[rest % 10]);
                } else if (rest > 0) {
                    part.add(BELOW_20[rest]);
                }
                if (!SCALES[scale].isEmpty()) part.add(SCALES[scale]);
                result.addAll(0, part);
            }
            num /= 1000;
            scale++;
        }
        return String.join(" ", result);
    }
}

Edge cases to test

  • num = 0
  • Teens 10-19, which have their own words
  • A whole group of zeros in the middle (1,000,005)
  • Exact round numbers (1,000,000,000) with no trailing words
  • The largest value 2,147,483,647

Hints

Hint 1

English names numbers in groups of three digits: units, Thousand, Million, Billion. Every group is spelled the same way.

Hint 2

Spell a number below 1000 as: hundreds digit + "Hundred", then either a word below 20 or a tens word followed by a ones word.

Hint 3

Skip any group equal to 0, and be careful not to leave double or trailing spaces.

FAQ

What is the best time complexity for Integer to English Words?

Optimal (iterative groups of three) runs in O(1) time and O(1) extra space. At most four groups, each spelled in constant time.

Which pattern does Integer to English Words use?

It is a arrays & hashing problem that uses the simulation pattern. Other problems with the same pattern: Text Justification, String to Integer (atoi), Remove Comments.

Is there a brute force solution for Integer to English Words?

Yes. Recursive descent by magnitude takes O(1) time and O(1) space. Write a function words(n) that peels off the largest unit it can: billions, millions, thousands, hundreds, tens, and finally the words below 20.

Which edge cases should I test for Integer to English Words?

num = 0; Teens 10-19, which have their own words; A whole group of zeros in the middle (1,000,005); Exact round numbers (1,000,000,000) with no trailing words; The largest value 2,147,483,647.