Convert a non-negative integer num to its English words representation.

&nbsp;
Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"


Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"


Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"


&nbsp;
Constraints:


	0 &lt;= num &lt;= 231 - 1


class Solution:
    def numberToWords(self, num: int) -> str:
        
        if num == 0:
            return "Zero"
        
        dic1 = {1000000000: "Billion", 1000000: "Million", 1000: "Thousand", 1: ""}
        dic2 = {90: "Ninety", 80: "Eighty", 70: "Seventy", 60: "Sixty", 50: "Fifty", 40: "Forty", 30: "Thirty", 20: "Twenty", 19: 'Nineteen', 18: "Eighteen", 17: "Seventeen", 16: "Sixteen", 15: "Fifteen", 14: "Fourteen", 13: "Thirteen", 12: "Twelve", 11: "Eleven", 10: "Ten", 9: "Nine", 8: "Eight", 7: "Seven", 6: "Six", 5: "Five", 4: "Four", 3: "Three", 2: "Two", 1: "One"}
        
        def construct_num(num):
            ans = ''
            d, num = divmod(num, 100)
            if d > 0:
                ans += dic2[d] + " " + "Hundred"
            for k, v in dic2.items():
                d, num = divmod(num, k)
                if d > 0:
                    ans += " " + v
            return ans.lstrip()                               
        
        ans = ""
        for k, v in dic1.items():
            d, num = divmod(num, k)
            if d > 0:
                ans += " " + construct_num(d) + " " + v
                
        return ans.strip()
class Solution {
    
    private static final int[] INT_NUMBERS = {
            1_000_000_000, 1_000_000, 1000, 100, 90, 80, 70, 60, 50, 40, 30, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    private static final String[] STRING_NUMBERS = {
            "Billion", "Million", "Thousand", "Hundred", "Ninety", "Eighty", "Seventy", "Sixty", "Fifty", "Forty", "Thirty", "Twenty",
            "Nineteen", "Eighteen", "Seventeen", "Sixteen", "Fifteen", "Fourteen", "Thirteen", "Twelve", "Eleven", "Ten",
            "Nine", "Eight", "Seven", "Six", "Five", "Four", "Three", "Two", "One"};

    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        return numberToWordsHelper(num).toString();
    }

    private StringBuilder numberToWordsHelper(int num) {
        StringBuilder sb = new StringBuilder();
        if (num == 0) return sb;
        for (int i = 0; i < INT_NUMBERS.length; i++) {
            if (num >= INT_NUMBERS[i]) {
                if (num >= 100) {
                    sb.append(numberToWordsHelper(num / INT_NUMBERS[i]).append(" "));
                }

                sb.append(STRING_NUMBERS[i]).append(" ").append(numberToWordsHelper(num % INT_NUMBERS[i]));
                break;
            }
        }
        return sb.charAt(sb.length() - 1) == ' ' ? sb.deleteCharAt(sb.length() - 1) : sb; // trim
    }
    
}
unordered_map<int, string> mp_0 = {{1, "One "},{2, "Two "},{3, "Three "},{4, "Four "},  {5, "Five "},{6, "Six "},{7, "Seven "},{8, "Eight "},{9, "Nine "}, {10, "Ten "},{11,"Eleven "},{12, "Twelve "},{13, "Thirteen "},{14, "Fourteen "},{15, "Fifteen "},{16, "Sixteen "},{17, "Seventeen "},{18, "Eighteen "},{19, "Nineteen "}};
        
unordered_map<int, string> mp_10 = {{20, "Twenty "},{30, "Thirty "},{40 , "Forty "},{50, "Fifty "},{60, "Sixty "},{70, "Seventy "},{80, "Eighty "},{90, "Ninety "}};

class Solution {
    
    void Solve2(string &ans , int num)
    {
       ans = mp_0[num] + ans;
    }
    
    void Solve( string &ans, int num)
    {
        int factor = 1;
        for(int i = 0 ; num>0 ; i++)
        {
            if(factor == 1)
            {
                
                if(num%100 < 20)
                {
                    Solve2(ans, num%100);
                    factor = factor*10;
                    num = num/10;
                }
                else
                {
                if(num%10 !=0)
                ans = mp_0[num%10] + ans;   
                }
            }
            
            else if(factor == 10)
            {
                if(num%10 != 0)
                   ans = mp_10[(num%10)*10] + ans;   
            }
            
            else if(factor == 100)
            {
                if(num%10 != 0)
                    ans = (mp_0[num%10] + "Hundred ") + ans;            
            }
            
            factor = factor*10;
            num = num/10;
        }
    }
public:
    string numberToWords(int num) {
        //2,147,483,647
        
        if(num == 0)
            return "Zero";
        
        string ans ;
        
       
        for(int i = 0 ; num>0 ; i++)
        {   
            if(i == 1)   
           { 
             if(num%1000>0)
             ans = "Thousand "+ ans;
           }
            else if(i == 2)
           { 
             if(num%1000>0)
             ans = "Million "+ ans;
           }
            else if( i == 3)
             ans = "Billion "+ ans;
            
            Solve(ans, num%1000);
            num = num/1000;
          
        }
                ans.pop_back();
        return ans;
        
        
    }
};
let numberMap = {
	0: 'Zero',
  100: 'Hundred',
  1: 'One',
  2: 'Two',
  3: 'Three',
  4: 'Four',
  5: 'Five',
  6: 'Six',
  7: 'Seven',
  8: 'Eight',
  9: 'Nine',
  10: 'Ten',
  11: 'Eleven',
  12: 'Twelve',
  13: 'Thirteen',
  14: 'Fourteen',
  15: 'Fifteen',
  16: 'Sixteen',
  17: 'Seventeen',
  18: 'Eighteen',
  19: 'Nineteen',
  20: 'Twenty',
  30: 'Thirty',
  40: 'Forty',
  50: 'Fifty',
  60: 'Sixty',
  70: 'Seventy',
  80: 'Eighty',
  90: 'Ninety'
};

let bigNumberMap = {
	1000000000: 'Billion',
  1000000: 'Million',
  1000: 'Thousand',
  1: 'One'
}

let bases = [];

for (let base in numberMap) {
	bases.push(parseInt(base, 10));
}
bases = bases.sort((a,b) => b-a);

let bigBases = [];
for (let base in bigNumberMap) {
	bigBases.push(parseInt(base, 10));
}
bigBases = bigBases.sort((a,b) => b-a);

var numberToWords = function(num) {
    let res = '';
    if (num === 0) return numberMap[num];
   	bigBases.forEach((base) => {
    	base = parseInt(base, 10);
      let baseAsString = base + '';
      let nums = num/base << 0;
      let remainder = num - nums * base;
      if (nums >= 1) {
    		[res, nums] = getForHundredBase(res, nums);
        res += baseAsString.length > 1 ? (' ' + bigNumberMap[base + '']) : '';
        num = remainder;
      }
    });
    return res;
};

function getForHundredBase(res, num) {
		bases.forEach((base) => {
    	base = parseInt(base, 10);
    	[num, res] = getNums(num, base, res);
    });
    return [res, num];
}

function getNums(num, base, res) {
	let nums = num / base << 0;
  let baseAsString = base + '';
  if (nums > 1 || (nums == 1 && baseAsString.length > 2)) {
  	res += res === '' ? res : " ";
  	res += numberMap[nums] + " " + numberMap[baseAsString];
  } else if (nums == 1) {
  	res += res === '' ? res : " ";
  	res += numberMap[baseAsString];
  }
  return [num - (nums * base), res];
}
Integer to English Words