<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 findDigit( vector<int> digits, int st, int end ){

        // cout<<"Attempting for "<<st<<" to "<<end<<" "<<digits[st]<<digits[st+1]<<digits[st+2]<<endl;
        // int num = 0;

        vector<string> digitStr = { "", "One", "Two", "Three","Four", "Five", "Six", "Seven", "Eight", "Nine" };

        vector<string> digitStrMain = { "Ten", "Eleven", "Twelve", "Thirteen","Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" };

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

        string finalStr = "";

        int dig = digits[st];

        if( dig > 0 ){
            finalStr += digitStr[dig] + " Hundred";
        }

        int num = digits[st+1] * 10 + digits[st+2];

        if( num == 0 && dig == 0 ) return "*"; 

        if( num > 0 && num < 10 ) finalStr += (dig != 0 ?  " "  : "") + digitStr[num];

        if( num >= 10 && num < 20 ) finalStr += (dig != 0 ?  " "  : "") + digitStrMain[num-10];
    
        if( num >= 20 && num <= 99 ) finalStr += (dig != 0 ?  " "  : "") + digitStrFinal[ (num/10) - 2 ] + (num % 10 != 0 ? " " + digitStr[num%10] : "");

        
 
        return finalStr;

    }

    string numberToWords(int num) {
        // cout<<INT_MAX<<endl;

        vector<int> digitPlaces( 12, 0 );

        int ind = 11;

        while( num > 0 ){
            int dig = num % 10;
            digitPlaces[ind] = dig;
            ind--;
            num = num / 10;
        }

        // for( int i=0 ; i<12 ; i++ ){
        //     cout<<digitPlaces[i];
        // }

        string ans = "";

        string findNum = findDigit( digitPlaces, 0, 2 );

        // cout<<" The number of billions is "<<findNum<<endl;

        if( findNum != "*" ){
            ans = (ans != "" ?  ans : "") + findNum + " " + "Billion ";
        }

        findNum = findDigit( digitPlaces, 3, 5 );

        // cout<<" The number of millions is "<<findNum<<endl;

        if( findNum != "*" ){
            ans = (ans != "" ?  ans : "") + findNum + " " + "Million ";
        }

        findNum = findDigit( digitPlaces, 6, 8 );

        // cout<<" The number of thousands is "<<findNum<<endl;

        if( findNum != "*" ){
            ans = (ans != "" ?  ans : "") + findNum + " " + "Thousand ";
        }

        findNum = findDigit( digitPlaces, 9, 11 );

        // cout<<" The number of digits is "<<findNum<<endl;

        if( findNum != "*" ){
            ans = (ans != "" ?  ans : "") + findNum + " ";
        }

        int len = ans.length();

        if( len > 1 )
            ans = ans.substr( 0, len-1 );
        else
            ans = "Zero";


        return ans;
    }
};
13600