Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ – 1.

Example 1:

Input: 123 
Output: "One Hundred Twenty Three" 

Example 2:

Input: 12345 
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567 
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" 

Example 4:

Input: 1234567891 
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Idea – 1

We can recursively process each named power of tens starting from the highest one going towards lowest, like process billions, then millions, then thousands, etc. Subhundreds have more variation in names like teens, twenties, thirties, etc. Since the input is an integer, basically this is a algorithm. However devil’s in details! For each named power of tens we have a quotient and a remainder. What if there is no remainder?

class Solution {
    private static final int[] units = {1000000000, 1000000, 1000, 100};
    private static final String[] names = {"Billion", "Million", "Thousand", "Hundred"};
    private static final String[] ones = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    
    private static final String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    private static final String[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    
    public String numberToWords(int num) {
        StringBuilder sb = new StringBuilder();
        if(num==0)
        {
            return "Zero";
        }        
        
        n2e(num, sb);
        
        return sb.toString().trim();
    }
    
    private void n2e(int num, StringBuilder sb)
    {
        for(int i = 0; i < units.length; ++i)
        {
            int unit = units[i];
            if(num >= unit)
            {
                n2e(num/unit, sb);
                sb.append(String.format(" %s", names[i]));
                
                num %= unit;
            }
        }
        
        if(num > 0)
        {
            int t = num/10;
            if(t == 0)
            {
                sb.append(String.format(" %s", ones[num]));
            }
            else if(t == 1)
            {
                sb.append(String.format(" %s", teens[num%10]));
            }
            else
            {
                sb.append(String.format(" %s", tens[t]));
                if(num%10 > 0)
                {
                    sb.append(String.format(" %s", ones[num%10]));    
                }
            }    
        }
    }
}


Runtime: 13 ms, faster than 6.23% of Java online submissions for Integer to English Words.
Memory Usage: 38.2 MB, less than 5.18% of Java online submissions for Integer to English Words.