<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:
    void appendOneToNineteen(int num, vector<string> &fragments) {
        switch(num) {
            case 1:
                fragments.push_back("One");
                num -= 1;
                break;
            case 2:
                fragments.push_back("Two");
                num -= 2;
                break;
            case 3:
                fragments.push_back("Three");
                num -= 3;
                break;
            case 4:
                fragments.push_back("Four");
                num -= 4;
                break;
            case 5:
                fragments.push_back("Five");
                num -= 5;
                break;
            case 6:
                fragments.push_back("Six");
                num -= 6;
                break;
            case 7:
                fragments.push_back("Seven");
                num -= 7;
                break;
            case 8:
                fragments.push_back("Eight");
                num -= 8;
                break;
            case 9:
                fragments.push_back("Nine");
                num -= 9;
                break;
            case 10:
                fragments.push_back("Ten");
                num -= 10;
                break;
            case 11:
                fragments.push_back("Eleven");
                num -= 11;
                break;
            case 12:
                fragments.push_back("Twelve");
                num -= 12;
                break;
            case 13:
                fragments.push_back("Thirteen");
                num -= 13;
                break;
            case 14:
                fragments.push_back("Fourteen");
                num -= 14;
                break;
            case 15:
                fragments.push_back("Fifteen");
                num -= 15;
                break;
            case 16:
                fragments.push_back("Sixteen");
                num -= 16;
                break;
            case 17:
                fragments.push_back("Seventeen");
                num -= 17;
                break;
            case 18:
                fragments.push_back("Eighteen");
                num -= 18;
                break;
            case 19:
                fragments.push_back("Nineteen");
                num -= 19;
                break;
        }
    }

    void appendBillion(int &num, vector<string> &fragments) {
        if (num / 1000000000 > 0) {
            appendOneToNineteen(num / 1000000000, fragments);
            fragments.push_back("Billion");
            num = num % 1000000000;
        }
    }

    void appendMillion(int &num, vector<string> &fragments) {
        if (num / 1000000 > 0) {
            int million = num / 1000000;
            appendHundred(million, fragments);
            fragments.push_back("Million");
            num = num % 1000000;
        }
    }

    void appendTens(int &num, vector<string> &fragments) {
        switch(num / 10) {
            case 2:
                fragments.push_back("Twenty");
                num -= 20;
                break;
            case 3:
                fragments.push_back("Thirty");
                num -= 30;
                break;
            case 4:
                fragments.push_back("Forty");
                num -= 40;
                break;
            case 5:
                fragments.push_back("Fifty");
                num -= 50;
                break;
            case 6:
                fragments.push_back("Sixty");
                num -= 60;
                break;
            case 7:
                fragments.push_back("Seventy");
                num -= 70;
                break;
            case 8:
                fragments.push_back("Eighty");
                num -= 80;
                break;
            case 9:
                fragments.push_back("Ninety");
                num -= 90;
                break;
        }
    }

    void appendThousand(int &num, vector<string> &fragments) {
        if (num / 1000 > 0) {
            int thousand = num / 1000;
            appendHundred(thousand, fragments);
            fragments.push_back("Thousand");
            num = num % 1000;
        }
    }

    void appendHundred(int &num, vector<string> &fragments) {
        if (num / 100 > 0) {
            int hundred = num / 100;
            appendOneToNineteen(hundred, fragments);
            fragments.push_back("Hundred");
            num = num % 100;
        }
        if (num >= 20) {
            appendTens(num, fragments);
            if (num > 0) {
                appendOneToNineteen(num, fragments);
            }
        } else if (num > 0) {
            appendOneToNineteen(num, fragments);
        }
    }

    void exportToResult(const vector<string> &fragments, string &result) {
        for (int i = 0; i < fragments.size(); ++i) {
            if (i > 0) {
                result += " ";
            }
            result += fragments[i];
        }
    }

    string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        string result;
        vector<string> fragments;
        appendBillion(num, fragments);
        appendMillion(num, fragments);
        appendThousand(num, fragments);
        appendHundred(num, fragments);
        exportToResult(fragments, result);
        return result;
    }
};
10800