public class Solution {

    private final String[] c = {"Billion", "Million", "Thousand", ""};

    private final String[] Tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

    private final String[] Basics = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};

    private String getField(int idx, int size) {

        if(size == 4) {

            if(idx == 0) return "Billion";

            else if(idx == 1) return "Million";

            else if(idx == 2) return "Thousand";

            else if(idx == 3) return "";

        }

        else if(size == 3) {

            if(idx == 0) return "Million";

            else if(idx == 1) return "Thousand";

            else if(idx == 2) return "";

        }

        else if(size == 2) {

            if(idx == 0) return "Thousand";

            else if(idx == 1) return "";

        }

        return "";

    }

    private LinkedList<String> read(int n) {

        LinkedList<String> rs = new LinkedList<String> ();

        int hundred = (n % 1000) / 100;

        int ten = (n % 100) / 10;

        int unit = n % 10;

        if(hundred > 0) {

            rs.addLast(Basics[hundred]);

            rs.addLast("Hundred");

        }

        if(ten > 0) {

            if(ten == 1) {

                int combo = ten * 10 + unit;

                rs.addLast(Basics[combo]);

                return rs;

            } else {

                rs.addLast(Tens[ten]);

            }

        }

        if(unit > 0) {

            rs.addLast(Basics[unit]);

        }

        return rs;

    }

    public String numberToWords(int num) {

        if(num == 0) {

            return "Zero";

        }

        LinkedList<Integer> d = new LinkedList<Integer> ();

        while(num > 0) {

            d.addFirst(num % 1000);

            num/=1000;

        }

        LinkedList<String> ls = new LinkedList<String> ();

        for(int i=0; i<d.size(); ++i) {

            if(d.get(i) == 0) continue;

            LinkedList<String> r = read(d.get(i));

            String field = getField(i, d.size());

            if(i == d.size() - 1) ls.addAll(r);

            else {

                ls.addAll(r);

                ls.addLast(field);

            }

        }

        StringBuffer rs = new StringBuffer();

        for(int i=0; i<ls.size() - 1; ++i) {

            rs.append(ls.get(i));

            rs.append(" ");

        }

        rs.append(ls.peekLast());

        return rs.toString().trim();

    }

}