<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 {
private:
    void append(string& s, const char *opnd, const char *&fs) {
        s += fs;
        fs = " ";

        s += opnd;
    }

public:
    string numberToWords(int num) {
        bool zf;
        const char *fs;
        const char *const *ones_tbl;
        int exp;
        int pow;
        string res;

        static const char *const ones[] = {
            [0] = "Zero",  [1] = "One",
            [2] = "Two",   [3] = "Three",
            [4] = "Four",  [5] = "Five",
            [6] = "Six",   [7] = "Seven",
            [8] = "Eight", [9] = "Nine"
        };

        static const char *const ten_to_nineteen[] = {
            [0] = "Ten",      [1] = "Eleven",
            [2] = "Twelve",   [3] = "Thirteen",
            [4] = "Fourteen", [5] = "Fifteen",
            [6] = "Sixteen",  [7] = "Seventeen",
            [8] = "Eighteen", [9] = "Nineteen"
        };

        static const char *const tens[] = {
            [2] = "Twenty", [3] = "Thirty",
            [4] = "Forty",  [5] = "Fifty",
            [6] = "Sixty",  [7] = "Seventy",
            [8] = "Eighty", [9] = "Ninety"
        };

        static const char *const powers[] = {
            [2] = "Hundred"
        };

        static const char *const powers_thousand[] = {
            [1] = "Thousand",
            [2] = "Million",
            [3] = "Billion"
        };

        exp = 0;
        pow = 10;
        for (;;) {
            if (num / pow == 0) {
                pow /= 10;
                break;
            }
            ++exp;
            if (INT_MAX / pow < 10)
                break;
            pow *= 10;
        }

        ones_tbl = ones;
        zf = true;
        fs = "";
        for (;;) {
            const char *s;
            int expm3;
            int val;

            val = num / pow % 10;
            if (val != 0)
                zf = false;
            expm3 = exp % 3;

            if (expm3 == 1) {
                s = tens[val];
                if (s != nullptr) {
                    append(res, s, fs);
                    ones_tbl = ones;
                } else if (val > 0)
                    ones_tbl = ten_to_nineteen;
            } else if (!zf || num == 0) {
                if (val > 0 || ones_tbl == ten_to_nineteen || num == 0)
                    append(res, ones_tbl[val], fs);
                if (expm3 != 0)
                    append(res, powers[expm3], fs);
                else {
                    if (exp > 0)
                        append(res, powers_thousand[exp / 3], fs);
                    zf = true;
                }
                ones_tbl = ones;
            }

            if (pow == 1)
                break;
            pow /= 10;
            --exp;
        }

        return res;
    }
};
7500