273. Integer to English Words

Description

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

Constraints

• 0 <= num <= 231 - 1

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

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"

Example 4

Input: num = 1234567891

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    
    private Map<Integer, String> map = new HashMap();
    private final String EMPTY = " ";
    
    public String numberToWords(int num) {
        loadMap();
        
        if(num <= 20) {
            return map.get(num);
        }
        
        StringBuilder result = new StringBuilder();
        
        if(num >= 1000000000) {
            int extra = num / 1000000000;
            result.append(convert(extra)).append(" Billion");
            num %= 1000000000;
        }
        
        if(num >= 1000000) {
            int extra = num / 1000000;
            result.append(convert(extra)).append(" Million");
            num %= 1000000;
        }
        
        if(num >= 1000) {
            int extra = num / 1000;
            result.append(convert(extra)).append(" Thousand");
            num %= 1000;
        }
        
        if(num > 0) {
            result.append(convert(num));
        }
        
        return result.toString().trim();
    }
    
    private String convert(int n) {
        StringBuilder result = new StringBuilder();
        
        if(n >= 100) {
            int nHundreds = n / 100;
            result.append(EMPTY).append(map.get(nHundreds)).append(" Hundred");
            n %= 100;
        }
        
        if(n > 0) {
            if(n <= 20) {
                result.append(EMPTY).append(map.get(n));
                n %= 100;
            } else {
                int nTens = n / 10;
                result.append(EMPTY).append(map.get(nTens * 10));
                n %= 10;
                
                if(n > 0) {
                    result.append(EMPTY).append(map.get(n));
                }
            }
        }
        
        return result.toString();
    }
    
    private void loadMap() {
        if(map.isEmpty()) {
            map.put(0, "Zero");
            map.put(1, "One");
            map.put(2, "Two");
            map.put(3, "Three");
            map.put(4, "Four");
            map.put(5, "Five");
            map.put(6, "Six");
            map.put(7, "Seven");
            map.put(8, "Eight");
            map.put(9, "Nine");
            map.put(10, "Ten");
            map.put(11, "Eleven");
            map.put(12, "Twelve");
            map.put(13, "Thirteen");
            map.put(14, "Fourteen");
            map.put(15, "Fifteen");
            map.put(16, "Sixteen");
            map.put(17, "Seventeen");
            map.put(18, "Eighteen");
            map.put(19, "Nineteen");
            map.put(20, "Twenty");
            map.put(30, "Thirty");
            map.put(40, "Forty");
            map.put(50, "Fifty");
            map.put(60, "Sixty");
            map.put(70, "Seventy");
            map.put(80, "Eighty");
            map.put(90, "Ninety");
        }
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

public class Solution {
    private final String[] belowTen = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    private final String[] belowTwenty = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] belowHundred = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

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

    private String helper(int num) {
        StringBuilder result = new StringBuilder();
        if (num < 10) {
            result.append(belowTen[num]);
        }
        else if (num < 20) {
            result.append(belowTwenty[num -10]);
        }
        else if (num < 100) {
            result.append(belowHundred[num/10]).append(" ").append(helper(num % 10));
        }
        else if (num < 1000) {
            result.append(helper(num/100)).append(" Hundred ").append(helper(num % 100));
        }
        else if (num < 1000000) {
            result.append(helper(num/1000)).append(" Thousand ").append(helper(num % 1000));
        }
        else if (num < 1000000000) {
            result.append(helper(num/1000000)).append(" Million ").append(helper(num % 1000000));
        }
        else {
            result.append(helper(num/1000000000)).append(" Billion ").append(helper(num % 1000000000));
        }
        return result.toString().trim();
    }
}

Follow up