<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>

class Solution {
public:
    string ones[20]={"", " One", " Two", " Three", " Four", " Five", " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve", " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", " Eighteen", " Nineteen"};
    string tens[10]={"", " Ten", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", " Seventy", " Eighty", " Ninety"};
    string thousands[4]={"", " Thousand", " Million", " Billion"};
    string f(int n)
    {
        if(n<20)
        {
            return ones[n];
        }
        if(n<100)
        {
            return tens[n/10]+f(n%10);
        }
        if(n<1000)
        {
            return f(n/100)+" Hundred"+f(n%100);
        }
        for(int i=3;i>=0;i--)
        {
            if(n>=pow(1000,i))
            {
                return f(n/pow(1000,i))+thousands[i]+f(n%(int)pow(1000,i));
            }
        }
        return "";
    }
    string numberToWords(int num) {
        if(num==0)
        {
            return "Zero";
        }
        return f(num).substr(1);
    }
};
10600