<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"};

string eng2[] = {"",      "Ten",   "Twenty",  "Thirty", "Forty",
                 "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

string eng3[] = {"", "Thousand", "Million", "Billion"};

string ans = "";

class Solution {

private:
    // function to process numbers below thousand;
    string toEnglish(int num) {

        string ans = "";
        int hundr = num / 100;
        if (hundr > 0) {
            ans += eng[hundr] + " Hundred ";
        }
        num = num % 100;
        if (num < 20) {
            ans += eng[num];
        } else {
            int ones = num % 10;
            int tens = num / 10;
            ans += eng2[tens] + " " + eng[ones];
        }

         if (!ans.empty() && ans.back() == ' ')
            ans.pop_back();
        return ans;

    }

public:
    string numberToWords(int num) {
        if (num == 0)
            return "Zero";

        string ans = "";
        int count = 0;

        while (num > 0) {
            int q = num / 1000;
            int r = num % 1000;
            num /= 1000;

            if(r > 0){
                string part = toEnglish(r) + " " + eng3[count];
                ans = (ans.empty()) ? part : part + " " + ans;
            }
            count++;
        }

         if (!ans.empty() && ans.back() == ' ') {
            ans.pop_back();
        }
        return ans;
    }
};
8500