<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 numberToWords(int num) {
                vector<int> numbers = {
                            1000000000, 1000000, 1000, 100, 90, 80, 70, 60, 50, 40, 30, 20,
                                        19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
                                                };  //31 numbers

                                                        vector<string> words = {
                                                                    "Billion", "Million", "Thousand", "Hundred", "Ninety", "Eighty",
                                                                                "Seventy", "Sixty", "Fifty", "Forty", "Thirty", "Twenty",
                                                                                            "Nineteen", "Eighteen", "Seventeen", "Sixteen", "Fifteen", "Fourteen",
                                                                                                        "Thirteen", "Twelve", "Eleven", "Ten", "Nine", "Eight", "Seven",
                                                                                                                    "Six", "Five", "Four", "Three", "Two", "One"
                                                                                                                            };

                                                                                                                                    string result;

                                                                                                                                            for(int i = 0; i < 31; i++){
                                                                                                                                                        if(num >= numbers[i]){
                                                                                                                                                                        if(num >= 100) result += numberToWords(num / numbers[i]) + " " + words[i] + " ";
                                                                                                                                                                                        else result += words[i] + " ";

                                                                                                                                                                                                        num %= numbers[i];

                                                                                                                                                                                                                        if (num == 0) break;
                                                                                                                                                                                                                                    }
                                                                                                                                                                                                                                            }

                                                                                                                                                                                                                                                    return result.empty() ? "Zero" : result.substr(0, result.size() - 1);
                                                                                                                                                                                                                                                        }
                                                                                                                                                                                                                                                        };
12500