class Solution {
    HashMap<Integer, String> base = new HashMap<>();
    public Solution() {
        base.put(0, "");
        base.put(1, "One ");
        base.put(2, "Two ");
        base.put(3, "Three ");
        base.put(4, "Four ");
        base.put(5, "Five ");
        base.put(6, "Six ");
        base.put(7, "Seven ");
        base.put(8, "Eight ");
        base.put(9, "Nine ");
        base.put(10, "Ten ");
        base.put(11, "Eleven ");
        base.put(12, "Twelve ");
        base.put(13, "Thirteen ");
        base.put(14, "Fourteen ");
        base.put(15, "Fifteen ");
        base.put(16, "Sixteen ");
        base.put(17, "Seventeen ");
        base.put(18, "Eighteen ");
        base.put(19, "Nineteen ");

        base.put(20, "Twenty ");
        base.put(30, "Thirty ");
        base.put(40, "Forty ");
        base.put(50, "Fifty ");
        base.put(60, "Sixty ");
        base.put(70, "Seventy ");
        base.put(80, "Eighty ");
        base.put(90, "Ninety ");
    }
    public String numberToWords(int num) {
        StringBuilder sb = new StringBuilder();
        int billions = num/1_000_000_000;
        if(billions != 0) {
            processUnder1000(billions, sb);
            sb.append("Billion ");
        }
        num %= 1_000_000_000;
        int millions = num/1_000_000;
        if(millions != 0) {
            processUnder1000(millions, sb);
            sb.append("Million ");
        }
        num %= 1_000_000;
        int thousands = num/1000;
        if(thousands != 0) {
            processUnder1000(thousands, sb);
            sb.append("Thousand ");
        }
        num %= 1000;
        processUnder1000(num, sb);
        if(sb.length() == 0) {
            return "Zero";
        } else {
            sb.setLength(sb.length() - 1);
            return sb.toString();
        }
    }

    void processUnder1000(int num, StringBuilder sb) {
        if(num < 20) {
            sb.append(base.get(num));
        } else {
            if(num > 99) {
                sb.append(base.get(num/100)).append("Hundred ");
                processUnder1000(num%100, sb);
            } else {
                num%=100;
                int rem = num%10;
                num -= rem;
                sb.append(base.get(num)).append(base.get(rem));
            }
        }
    }
}