class Solution {
    private static String[] ONES_AND_TEENS = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private static String[] TENS = {null, "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private static String HUNDRED = "Hundred";
    private static String[] HIGHER_ORDERS = {null, "Thousand", "Million", "Billion"};

    public String numberToWords(int num) {
        if (num < 20) {
            return ONES_AND_TEENS[num];
        }

        Deque<String> stack = new LinkedList<>();

        // Work from right to left
        int quotient = num;
        int i=0;
        while (quotient > 0) {
            String suffix = HIGHER_ORDERS[i];
            if (suffix != null) {
                stack.push(suffix);
            }
            String tens = getTens(quotient);
            if (tens != null) {
                stack.push(tens);
            }
            String hundreds = getHundreds(quotient);
            if (hundreds != null) {
                stack.push(hundreds);
            }
            quotient = quotient / 1000;
            i++;
        }

        return String.join(" ", stack);
    }

    private static String getOnesAndTeens(int num) {
        return ONES_AND_TEENS[num];
    }

    private static String getHundreds(int num) {
        String hundreds = null;
        int hundredsPlace = (num % 1000) / 100;
        if (hundredsPlace > 0) {
            hundreds = getOnesAndTeens(hundredsPlace) + " " + HUNDRED;
        }

        return hundreds;
    }

    private static String getTens(int num) {
        String tens = null;
        int remainder = num % 100;
        if (remainder < 20) {
            tens = getOnesAndTeens(remainder);
        } else {
            int tensPlace = remainder / 10;
            tens = TENS[tensPlace];
            int onesPlace = remainder % 10;
            if (onesPlace > 0) {
                tens += " " + ONES_AND_TEENS[onesPlace];
            }
        }

        return tens;
    }
}