<p>Convert a non-negative integer <code>num</code> to its English words representation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = 123
<strong>Output:</strong> &quot;One Hundred Twenty Three&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = 12345
<strong>Output:</strong> &quot;Twelve Thousand Three Hundred Forty Five&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = 1234567
<strong>Output:</strong> &quot;One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= num &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

string eng[] = {"",        "One",     "Two",       "Three",    "Four",
                "Five",    "Six",     "Seven",     "Eight",    "Nine",
                "Ten",     "Eleven",  "Twelve",    "Thirteen", "Fourteen",
                "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen",
                "Twenty",  "Thirty",  "Forty",     "Fifty",    "Sixty",
                "Seventy", "Eighty",  "Ninety",    "Hundred",  "Thousand",
                "Million", "Billion"};
int digit[] = {0,  1,  2,  3,  4,  5,  6,   7,    8,       9,         10,
               11, 12, 13, 14, 15, 16, 17,  18,   19,      20,        30,
               40, 50, 60, 70, 80, 90, 100, 1000, 1000000, 1000000000};

class Solution {
public:
    static string numberToWords(int num, int cnt=0) {
        if (num == 0) return (cnt==0)?"Zero":"";
        if (num<=20) return eng[num];
        int i=upper_bound(digit, end(digit), num)-digit-1;
        auto [q, r]=div(num, digit[i]);
        string ans="";
        if (digit[i]>=100)
            ans+= numberToWords(q, cnt+1)+" "+eng[i];
        else ans=eng[i];
        if (r>0) ans+=" " + numberToWords(r, cnt+1);
        
        return ans;
    }
};
9400