<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) {
        if (num == 0){
            return "Zero";
        }
        vector<string> ones_hundreds = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
        vector<string> tens_m1 = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        vector<string> tens_1 = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        vector<string> x1000 = {"", "Thousand", "Million", "Billion"};
        vector<string> results;
        int x1000_idx = 0;
        while(num){
            
            int ones = num % 10;
            num /= 10;
            int tens = num % 10;
            num /= 10;
            int hundreds = num % 10;
            num /= 10;
            if (ones || tens || hundreds){
                results.push_back(x1000[x1000_idx]);
            }
            
            if (tens != 1){
                results.push_back(ones_hundreds[ones]);
                results.push_back(tens_m1[tens]);
                if (hundreds){
                    results.push_back("Hundred");
                }
                results.push_back(ones_hundreds[hundreds]);
                
            }
            else{
                results.push_back(tens_1[ones]);
                if (hundreds){
                    results.push_back("Hundred");
                }
                results.push_back(ones_hundreds[hundreds]);
            }
            x1000_idx++;
        }
        string result = "";
        for (int i = results.size()-1; i>=0; i--){
            if (results[i] != ""){
                result += results[i];
                result += " ";
            }
        }
        while(result.back() == ' '){
            result.pop_back();
        }
        return result;
    }
};
11400