# Question

Formatted question description: https://leetcode.ca/all/273.html

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

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"


Constraints:

• 0 <= num <= 231 - 1

# Algorithm

The highest can only reach billions, and a group of 3 can only handle 4 groups.

Then we need some function to process three groups of numbers

• We need to list all English words from 1 to 19 and put them in an array
• Also list the English words from 20, 30,… to 90 in another array,

Then, a three-digit n, the hundreds digit is expressed as n/100, the last two digits together are expressed as n%100, the tens digit is expressed as n%100/10, and the single digit is expressed as n%10

Then we see if the last two digits are less than 20

• If it is less than, take the word directly from the array
• If it is greater than or equal to 20, then take the ten and one digit words from the two arrays respectively

Then deal with the number on the hundreds, and remember to add Hundred.

Call this helper function four times in the main function, then insert “Thousand”, “Million”, “Billion” in the middle to the corresponding position, and finally check whether there are spaces at the end, delete all spaces, and check the input when returning whether it is 0, if yes, return ‘Zero’.

# Code

• import java.util.Arrays;
import java.util.List;

public class Integer_to_English_Words {

public static void main(String[] args) {
Integer_to_English_Words out = new Integer_to_English_Words();
Solution s = out.new Solution();

System.out.println(s.numberToWords(123));
System.out.println(s.numberToWords(1234567891));
}

class Solution {

List<String> v1 = Arrays.asList("", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen");
List<String> v2 = Arrays.asList("", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety");

public String numberToWords(int num) {

String res = convertHundred(num % 1000);
List<String> unit = Arrays.asList("Thousand", "Million", "Billion", "Trillion");
for (int i = 0; i < 3; ++i) {
num /= 1000;
res = num % 1000 != 0 ? convertHundred(num % 1000) + " " + unit.get(i) + " " + res : res;
}

res = res.trim();

return res.isEmpty() ? "Zero" : res;
}

String convertHundred(int num) {

String res;
int a = num / 100, b = num % 100, c = num % 10;

res = b < 20 ?
v1.get(b)
: v2.get(b / 10) + (c != 0 ? " " + v1.get(c) : "");
if (a > 0) {
res = v1.get(a) + " Hundred" + (b != 0 ? " " + res : "");
}

return res;
}
}
}

############

class Solution {
private static Map<Integer, String> map;

static {
map = new HashMap<>();
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");
map.put(4, "Four");
map.put(5, "Five");
map.put(6, "Six");
map.put(7, "Seven");
map.put(8, "Eight");
map.put(9, "Nine");
map.put(10, "Ten");
map.put(11, "Eleven");
map.put(12, "Twelve");
map.put(13, "Thirteen");
map.put(14, "Fourteen");
map.put(15, "Fifteen");
map.put(16, "Sixteen");
map.put(17, "Seventeen");
map.put(18, "Eighteen");
map.put(19, "Nineteen");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");
map.put(60, "Sixty");
map.put(70, "Seventy");
map.put(80, "Eighty");
map.put(90, "Ninety");
map.put(100, "Hundred");
map.put(1000, "Thousand");
map.put(1000000, "Million");
map.put(1000000000, "Billion");
}

public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
StringBuilder sb = new StringBuilder();
for (int i = 1000000000; i >= 1000; i /= 1000) {
if (num >= i) {
sb.append(get3Digits(num / i)).append(' ').append(map.get(i));
num %= i;
}
}
if (num > 0) {
sb.append(get3Digits(num));
}
return sb.substring(1);
}

private String get3Digits(int num) {
StringBuilder sb = new StringBuilder();
if (num >= 100) {
sb.append(' ').append(map.get(num / 100)).append(' ').append(map.get(100));
num %= 100;
}
if (num > 0) {
if (num < 20 || num % 10 == 0) {
sb.append(' ').append(map.get(num));
} else {
sb.append(' ').append(map.get(num / 10 * 10)).append(' ').append(map.get(num % 10));
}
}
return sb.toString();
}
}


• // OJ: https://leetcode.com/problems/integer-to-english-words/
// Time: O(lgN)
// Space: O(lgN)
class Solution {
const string one[9] = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
const string teen[10] = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
const string ty[10] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
const string segments[3] = {"Thousand", "Million", "Billion"};
public:
string numberToWords(int num) {
if (num == 0) return "Zero";
vector<string> ans;
int segIndex = -1;
for (; num; num /= 1000) {
int digits[3] = {}, segment = num % 1000;
if (segIndex > -1 && segment) ans.push_back(segments[segIndex]);
++segIndex;
for (int i = 0; i < 3 && segment; ++i) {
digits[i] = segment % 10;
segment /= 10;
}
if (digits[1] != 1 && digits[0]) ans.push_back(one[digits[0] - 1]);
if (digits[1] == 1) {
ans.push_back(teen[digits[0]]);
} else if (digits[1] > 1) {
ans.push_back(ty[digits[1] - 2]);
}
if (digits[2]) {
ans.push_back("Hundred");
ans.push_back(one[digits[2] - 1]);
}
}
string merged;
for (int i = ans.size() - 1; i >= 0; --i) {
if (merged.size()) merged += " ";
merged += ans[i];
}
return merged;
}
};

• '''
In Python 3. x and latest 2. x, floor division for both integer arguments and floating-point arguments is achieved by using the double slash ("//") operator

>>> print(0.6/0.2)
3.0
>>> print(0.6//0.2)
2.0

>>> 3.0 / 2.0
1.5
>>>
>>> 3.0 // 2.0
1.0
'''
class Solution:
def numberToWords(self, num: int) -> str:
if num == 0:
return 'Zero'

lt20 = [
'',
'One',
'Two',
'Three',
'Four',
'Five',
'Six',
'Seven',
'Eight',
'Nine',
'Ten',
'Eleven',
'Twelve',
'Thirteen',
'Fourteen',
'Fifteen',
'Sixteen',
'Seventeen',
'Eighteen',
'Nineteen',
]
tens = [
'',
'Ten',
'Twenty',
'Thirty',
'Forty',
'Fifty',
'Sixty',
'Seventy',
'Eighty',
'Ninety',
]
thousands = ['Billion', 'Million', 'Thousand', ''] # reversed order

def transfer(num):
if num == 0:
return ''
if num < 20:
return lt20[num] + ' '
if num < 100:
return tens[num // 10] + ' ' + transfer(num % 10)
return lt20[num // 100] + ' Hundred ' + transfer(num % 100) # 100-999

res = []
i, j = 1000000000, 0 # i is 1 billion, j is index of thousands[] list
while i > 0:
if num // i != 0:
res.append(transfer(num // i))
res.append(thousands[j])
res.append(' ')
num %= i
j += 1
i //= 1000
return ''.join(res).strip()

############

units = {1: "", 100: " Hundred", 1000: " Thousand", 1000000: " Million", 1000000000: " Billion"}
tenToTwenty = {10: "Ten", 11: "Eleven", 12: "Twelve", 13: "Thirteen", 14: "Fourteen", 15: "Fifteen", 16: "Sixteen",
17: "Seventeen", 18: "Eighteen", 19: "Nineteen", 20: "Twenty"}
tens = {2: "Twenty", 3: "Thirty", 4: "Forty", 5: "Fifty", 6: "Sixty", 7: "Seventy", 8: "Eighty", 9: "Ninety"}
digit = {1: "One", 2: "Two", 3: "Three", 4: "Four", 5: "Five", 6: "Six", 7: "Seven", 8: "Eight", 9: "Nine", 10: "Ten"}

class Solution(object):
def numberToWords(self, num):
"""
:type num: int
:rtype: str
"""
global units, tenToTwenty, tens, digit
ans = []

def getNum(number):
global units, tenToTwenty, tens, digit
divider = 1000
ans = []
h = number / 100
if h != 0:
ans.append(digit[h] + " Hundred")
number = number % 100
if number in tenToTwenty:
ans.append(tenToTwenty[number])
else:
t = number / 10
if t != 0:
ans.append(tens[t])
number = number % 10
d = number
if d != 0:
ans.append(digit[d])
return " ".join(ans)

divider = 1000000000
while num > 0:
res = num / divider
if res != 0:
ans.append(getNum(res) + units[divider])
num = num % divider
divider /= 1000
if not ans:
return "Zero"
return " ".join(ans)


• using System.Collections.Generic;
using System.Linq;

public class Solution {
private string[] bases = { "Thousand", "Million", "Billion" };
public string NumberToWords(int num) {
if (num == 0)
{
return "Zero";
}
var baseIndex = -1;
var parts = new List<string>();
while (num > 0)
{
var part = NumberToWordsInternal(num % 1000);
if (part.Length > 0 && baseIndex >= 0)
{
part = JoinParts(part, bases[baseIndex]);
}
baseIndex++;
num /= 1000;
}
parts.Reverse();
return JoinParts(parts);
}

private string JoinParts(IEnumerable<string> parts)
{
return string.Join(" ", parts.Where(p => p.Length > 0));
}

private string JoinParts(params string[] parts)
{
return JoinParts((IEnumerable<string>)parts);
}

private string NumberToWordsInternal(int num)
{
switch(num)
{
case 0: return "";
case 1: return "One";
case 2: return "Two";
case 3: return "Three";
case 4: return "Four";
case 5: return "Five";
case 6: return "Six";
case 7: return "Seven";
case 8: return "Eight";
case 9: return "Nine";
case 10: return "Ten";
case 11: return "Eleven";
case 12: return "Twelve";
case 13: return "Thirteen";
case 14: return "Fourteen";
case 15: return "Fifteen";
case 16: return "Sixteen";
case 17: return "Seventeen";
case 18: return "Eighteen";
case 19: return "Nineteen";
}

if (num < 100)
{
string part1;
switch (num/10)
{
case 2: part1 = "Twenty"; break;
case 3: part1 = "Thirty"; break;
case 4: part1 = "Forty"; break;
case 5: part1 = "Fifty"; break;
case 6: part1 = "Sixty"; break;
case 7: part1 = "Seventy"; break;
case 8: part1 = "Eighty"; break;
case 9: default: part1 = "Ninety"; break;
}
var part2 = NumberToWordsInternal(num % 10);
return JoinParts(part1, part2);
}

{
var part1 = NumberToWordsInternal(num / 100);
var part2 = NumberToWordsInternal(num % 100);
return JoinParts(part1, "Hundred", part2);
}
}
}