/*
1. 首先确定单位和数的映射：1~9， 11~19， 10，20，……，80，90， 1e2, 1e4, 1e6, 1e9
2. 按单位大小 从大到小开始递归处理
2.1 dfs 顺序： 按单位切分成左右两段数字递归处理，理论上可以处理任何单位的数
2.2 dfs 状态：待处理的数字

2.3 边界条件：  （非常多）
2.3.1： 0的时候
2.3.2： 1，2，…… 19
2.3.3： >= 100 时 格式为 “One” Hunder，而 <100 时不加
2.3.4：划分恰好为倍数的情况
2.3.5：划分恰好等于单位的情况

3. testcase:  0, 1, 9, 14, 79, 100 ,200 ,330, 333, 1234, 4004, 1234567891

*/


class Solution {
    int[] units = {1000000000, 1000000, 1000, 100, 90, 80, 70, 60, 50, 40, 30, 20};
    Map<Integer, String> mapping = initMapping();

    public String numberToWords(int num) {

        int index = lowerBound(units, num);
        int unit = units[index];
        String unitEnglish = mapping.get(unit);
         if (num > unit){
            int tail = num % unit;
            int head = num / unit;

            String prefix = numberToWords(head);
            if (tail == 0) return String.format("%s %s", prefix, unitEnglish);;

            String suffix = numberToWords(tail);
            if (num < 100) return String.format("%s %s", unitEnglish, suffix);

            return String.format("%s %s %s", prefix, unitEnglish, suffix);
        } else if (num == unit) {
            return num < 100 ? unitEnglish : ("One " + unitEnglish);
        } else{
            return mapping.get(num);
        }
    }

    public int lowerBound(int[] array, int target){
        int l = 0 , r = array.length - 1;
        while (l < r){
            int mid = l + r >> 1;
            if (array[mid] > target) l = mid + 1;
            else r = mid ;
        }
        return l;
    }

    public Map<Integer, String> initMapping() {
        Map<Integer, String> mapping = new HashMap<>();
        mapping.put(0, "Zero");
        mapping.put(1, "One");
        mapping.put(2, "Two");
        mapping.put(3, "Three");
        mapping.put(4, "Four");
        mapping.put(5, "Five");
        mapping.put(6, "Six");
        mapping.put(7, "Seven");
        mapping.put(8, "Eight");
        mapping.put(9, "Nine");

        mapping.put(11, "Eleven");
        mapping.put(12, "Twelve");
        mapping.put(13, "Thirteen");
        mapping.put(14, "Fourteen");
        mapping.put(15, "Fifteen");
        mapping.put(16, "Sixteen");
        mapping.put(17, "Seventeen");
        mapping.put(18, "Eighteen");
        mapping.put(19, "Nineteen");

        mapping.put(10, "Ten");
        mapping.put(20, "Twenty");
        mapping.put(30, "Thirty");
        mapping.put(40, "Forty");
        mapping.put(50, "Fifty");
        mapping.put(60, "Sixty");
        mapping.put(70, "Seventy");
        mapping.put(80, "Eighty");
        mapping.put(90, "Ninety");

        mapping.put(100, "Hundred");
        mapping.put(1000, "Thousand");
        mapping.put(1000000, "Million");
        mapping.put(1000000000, "Billion");
        return mapping;
    }

}