Problem

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

Examples

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"

Constraint

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

Solution

Method 1 - Using Lookup Table and Recursion 🏆

To solve the problem of converting a non-negative integer to its English words representation, we need to break down the number into manageable parts and process each part individually. This problem requires handling different ranges of numbers separately, such as units, tens, hundreds, thousands, millions, etc.

Video Explanation

Here is the video explanation:

Code

Java
Compare smaller values first
class Solution {

     private static final String[] BELOW_TWENTY = {
         "", "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"
     };
 
    final int BILLION = 1000_000_000;
    final int MILLION = 1000_000;
    final int THOUSAND = 1000;
    final int HUNDRED = 100;

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

        return helper(num);
    }

    private String helper(int num) {
        String ans = "";

        if (num < 20) {
            ans = BELOW_TWENTY[num];
        } else if (num < 100) {
            ans = TENS[num / 10] + " " + helper(num % 10);
        }
        else if (num < THOUSAND) {
            ans = helper(num / HUNDRED) + " Hundred " + helper(num % HUNDRED);
        } else if (num < MILLION) {
            ans = helper(num / THOUSAND) + " Thousand " + helper(num % THOUSAND);
        } else if (num < BILLION) {
            ans = helper(num / MILLION) + " Million " + helper(num % MILLION);
        } else {
            ans = helper(num / BILLION) + " Billion " + helper(num % BILLION);
        }

        return ans.trim();
    }
 }
Compare Larger Values First
class Solution {

     private static final String[] BELOW_TWENTY = {
         "", "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"
     };


	final String[] radixEnglish = {"Billion", "Million", "Thousand", "Hundred"};
	final int[] radix = {1000_000_000, 1000_000, 1000, 100};

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

        return helper(num).trim();
    }

    private String helper(int num) {
        for (int i = 0; i < radix.length; i++) {
            int divisor = radix[i];
            if (num >= radix[i]) {
                return (helper(num / divisor) + " " + radixEnglish[i] + " " + helper(num % divisor)).trim();
            }


        }

        if (num >= 20) {
            return (TENS[num / 10] + " " + helper(num % 10)).trim();
        }
        return BELOW_TWENTY[num];
    }
}

Some Test Cases

Some test cases for this problem:

  • Start with easy case, just to see if it’s working properly like 1234
  • Zero
  • All numbers are the same digit like 1111
  • All numbers are different digits
  • A number with a lot of zeros like 500, 000; 30, 000, 100,000; 2000, 100, 90.
  • At least one number in the teens (11-19)
  • Numbers with zeros in the middle, like 500008
  • Numbers less than 1000
  • Numbers less than 100 like 89

Summary

Although this is our custom program, but in real life we shouldn’t reinvent the wheel and its best to use already-implemented functions to perform this. ICU4J contains a class com.ibm.icu.text. RuleBasedNumberFormat that can be used to perform this operation. It also supports languages other than English, and the reverse operation, parsing a text string to integer values.