<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 ntw(int num){
        string ans;
        int x=num/100;
        int y=(num/10)%10;
        int z=num%10;
        if(x!=0){
            if(x==1) ans+="One ";
            else if(x==2) ans+="Two ";
            else if(x==3) ans+="Three ";
            else if(x==4) ans+="Four ";
            else if(x==5) ans+="Five ";
            else if(x==6) ans+="Six ";
            else if(x==7) ans+="Seven ";
            else if(x==8) ans+="Eight ";
            else if(x==9) ans+="Nine ";
            ans+="Hundred ";
        }
        if(y!=0){
            if(y==2) ans+="Twenty ";
            else if(y==3) ans+="Thirty ";
            else if(y==4) ans+="Forty ";
            else if(y==5) ans+="Fifty ";
            else if(y==6) ans+="Sixty ";
            else if(y==7) ans+="Seventy ";
            else if(y==8) ans+="Eighty ";
            else if(y==9) ans+="Ninety ";
        }
        if(y==1){
            if(z==0) ans+="Ten ";
            else if(z==1) ans+="Eleven ";
            else if(z==2) ans+="Twelve ";
            else if(z==3) ans+="Thirteen ";
            else if(z==4) ans+="Fourteen ";
            else if(z==5) ans+="Fifteen ";
            else if(z==6) ans+="Sixteen ";
            else if(z==7) ans+="Seventeen ";
            else if(z==8) ans+="Eighteen ";
            else if(z==9) ans+="Nineteen ";
        }else if(z!=0){
            if(z==1) ans+="One ";
            else if(z==2) ans+="Two ";
            else if(z==3) ans+="Three ";
            else if(z==4) ans+="Four ";
            else if(z==5) ans+="Five ";
            else if(z==6) ans+="Six ";
            else if(z==7) ans+="Seven ";
            else if(z==8) ans+="Eight ";
            else if(z==9) ans+="Nine ";
        }
        return ans;
    }
    string numberToWords(int num) {
        if(num==0) return "Zero";
        int x=num;
        int n=0;
        while(x>0){
            x/=10;
            n++;
        }
        x=num;
        vector<int> v;
        int y=0;
        int f=1;
        for(int i=1;i<=n;i++){
            y+=(f*(x%10));
            f*=10;
            x=x/10;
            if(i%3==0 || i==n){
                v.push_back(y);
                y=0;
                f=1;
            }
        }
        string fans;
        for(int i=v.size()-1;i>=0;i--){
            string t=ntw(v[i]);
            fans+=t;
            if(n>9 && v[i]>0) fans+="Billion ";
            else if(n>6 && v[i]>0) fans+="Million ";
            else if(n>3 && v[i]>0) fans+="Thousand ";
            n-=3;
        }
        string ans;
        cout<<fans;
        for(int i=0;i<fans.size()-1;i++){
            ans+=fans[i];
        }
        return ans;
    }
};
8000