<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:
    vector<string> lessThan20 = {
        "Zero",
        "One",
        "Two",
        "Three",
        "Four",
        "Five",
        "Six",
        "Seven",
        "Eight",
        "Nine",
        "Ten",
        "Eleven",
        "Twelve",
        "Thirteen",
        "Fourteen",
        "Fifteen",
        "Sixteen",
        "Seventeen",
        "Eighteen",
        "Nineteen",
    };

    vector<string> tens = {
        "",
        "",
        "Twenty",
        "Thirty",
        "Forty",
        "Fifty",
        "Sixty",
        "Seventy",
        "Eighty",
        "Ninety",
    };

    string numberToWords(int num) {
        if (num < 20) {
            return lessThan20[num];
        }

        vector<pair<int, string>> units = {
            {1000000000, "Billion"},
            {1000000, "Million"},
            {1000, "Thousand"},
            {100, "Hundred"}
        };

        for (auto& p : units) {
            int ammount = p.first;
            string unit = p.second;
            if (num >= ammount) {
                string x = numberToWords(num / ammount);
                x += " " + unit;
                if (num % ammount) {
                    x += " " + numberToWords(num % ammount);
                }
                return x;
            }
        }

        string x = tens[num/10];
        if (num % 10) {
            x += " " + numberToWords(num % 10);
        }
        return x;
    }
};
12400